博客昵称：沈小农学编程
作者简介：一名在读硕士，定期更新相关算法面试题，欢迎关注小弟！
PS：哈喽！各位CSDN的uu们，我是你的小弟沈小农，希望我的文章能帮助到你。欢迎大家在评论区唠嗑指正，觉得好的话别忘了一键三连哦！😘
题目难度：简单
默认优化目标：最小化时间复杂度。
Python默认为Python3。
1 题目描述
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的 字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram" 输出: true
示例 2:
输入: s = "rat", t = "car" 输出: false
提示:
-
1 <= s.length, t.length <= 5 * 104 -
s和t仅包含小写字母
2 题目解析
首先我们要搞清楚异位词是什么。[异位词]可以等价于[两个字符串排序后相等]，也可以等价于[两个字符串中各字符数量相等]。针对这两种等价方式，我们可以使用排序法和哈希表法。
这道题目中输入是两个字符串s和t，输出是bool值。
3 代码实现
3.1 排序法
我们先将s和t进行排序，然后比较这两个字符串是否相等。相等输出true，反之false。
时间复杂度O(n*log n)，空间复杂度O(log n)。
C++代码实现
class Solution {
public:bool isAnagram(string s, string t) {if(s.size()!=t.size()){return false;}sort(s.begin(),s.end());sort(t.begin(),t.end());
return s==t;}
};Python代码实现
class Solution:def isAnagram(self, s: str, t: str) -> bool:if len(s)!=len(t):return Falsereturn sorted(s)==sorted(t)3.2 哈希表法
我们创建两个哈希表记录s和t中的字符出现频次，比较它们是否相等。是则true，否则false。进一步简化，我们只需要一个哈希表记录s中的字符出现次数，然后再减去t中的对应的字符出现次数，只要出现负数，返回false；否则返回true。
时间复杂度O(n)，空间复杂度O(1)。
C++代码实现
class Solution {
public:bool isAnagram(string s, string t) {if(s.size()!=t.size()){return false;}vector<int> table(26,0);for(auto& ch:s){table[ch-'a']++;}for(auto& ch:t){table[ch-'a']--;if(table[ch-'a']<0){return false;}}return true;}
};Python代码
class Solution:def isAnagram(self, s: str, t: str) -> bool:if len(s)!=len(t):return Falsetable=[0]*26for ch in s:table[ord(ch)-ord('a')]+=1for ch in t:table[ord(ch)-ord('a')]-=1if table[ord(ch)-ord('a')]<0:return Falsereturn True另外一种一行代码解决方案
class Solution:def isAnagram(self, s: str, t: str) -> bool:return Counter(s)==Counter(t)参考文献
力扣面试经典150题
力扣官方题解
