有效的字母异位词

本节对应代码随想录中：代码随想录，讲解视频：学透哈希表，数组使用有技巧！Leetcode：242.有效的字母异位词_哔哩哔哩_bilibili

习题

题目链接：242. 有效的字母异位词 - 力扣（LeetCode）

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词，s 和 t 仅包含小写字母。

示例 1:
输入: s = “anagram”, t = “nagaram”
输出: true

示例 2:
输入: s = “rat”, t = “car”
输出: false

进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

排序

先对两个字符串排序，然后就可以直接比较两个字符串是否相等

class Solution {
public:bool isAnagram(string s, string t) {if (s.length() != t.length()) {return false;}sort(s.begin(), s.end());sort(t.begin(), t.end());return s == t;}
};

• 时间复杂度：O(nlogn)。其中 n 为字符串的长度。因为使用了排序函数，排序的时间复杂度为 O(nlogn)。字符串比较的时间复杂度为 O(n)，因此总时间复杂度为 O(nlogn + n) = O(nlogn)。
• 空间复杂度：O(log n)。其中 n 为字符串的长度。排序需要使用 O(logn) 的栈空间，因此空间复杂度为 O(logn)。

我的解法

既然 s 和 t 都仅包含小写字母，那就可以分别定义两个数组，用来存对应字符的出现次数，如果两个数组对应位置的数值一样那就是 true。同时如果两个字符串长度不同，可以直接返回 false

class Solution {public:bool isAnagram(string s, string t) {// 两个字符若长度不等直接返回falseint size = s.length();if (size != t.length()) {return false;}int num_s[26] = {0};int num_t[26] = {0};// 遍历字符串，两个计数的数组计数for (int i = 0; i < size; i++) {num_s[int(s[i]) - 97] += 1;num_t[int(t[i]) - 97] += 1;}// 一旦某一个字符的次数不一样直接返回falsefor (int i = 0; i < 26; i++) {if (num_s[i] != num_t[i]) {return false;}}return true;}
};

• 时间复杂度：O(n)。其中 n 为字符串的长度。遍历字符串需要 O(n) 的时间，计数数组的遍历需要 O(1) 的时间，因此总时间复杂度为 O(n)。
• 空间复杂度：O(1)。由于只使用了长度为 26 的计数数组，空间复杂度是常数级别的。

可以优化的点

• int(s[i]) - 97 可以替换为 s[i] - 'a'，这样无需记住字符 a 的 ASCII

哈希表

其实我的解法也属于哈希表，不过其实不需要两个数组来计数，只需要一个数组统计其中一个字符串，然后遍历另一个字符串的时候对应位置的数值减1，如果对应位置数值<0，说明 t 的这个位置的元素比 s 的多，则返回 false

例如，s 为 aab，t 为 aaa。遍历到 t 的第二个 a 的时候，table[0]已经等于0了，当遍历到 t 的第三个 a 的时候，table[0]=-1<0，说明 t 中的 a 比 s 中的 a 至少多一个(后面可能还会有更多的 a，但没必要再去遍历了)。

代码随想录中是先遍历 t，对应位置减1，再判断数组是否全为0，但下面这种解法只需使用两个 for 循环，比代码随想录上的3个 for 循环更优

class Solution {
public:bool isAnagram(string s, string t) {if (s.length() != t.length()) {return false;}int table[26] = {0};// 数组计数for (int i = 0; i < s.length(); i++) {table[s[i] - 'a']++;}for (int i = 0; i < t.length(); i++) {// 遍历字符串t对应位置减1table[t[i] - 'a']--;// 如果<0说明这个位置t的比s的多，即多减了一次if (table[t[i] - 'a'] < 0) {return false;}}return true;}
};

• 时间复杂度：O(n)。其中n为字符串的长度，需要遍历两个字符串，以及进行常数次的数组操作。
• 空间复杂度：O(1)。因为使用了一个大小为26的数组来存储每个字母出现的次数，空间大小与输入的字符串长度无关。

进阶解法

如果输入字符串包含 unicode 字符，那么可能的字符就不再是26个，没法使用大小为26的数组进行计数。此时就需要使用 unordered_map 了。

思路和上面的哈希表的差不多，先遍历 s，将其每个元素放进哈希表中。再遍历字符串 t，如果某个元素的次数<0说明 t 的这个位置的元素比 s 的多，则返回 false。只不过哈希表解法计数是根据字符-a 找索引，而这个是根据 key 直接找索引

class Solution {public:bool isAnagram(string s, string t) {if (s.size() != t.size()) {  // 先判断两个字符串长度是否相同return false;}unordered_map hash;  // 定义哈希表for (int i = 0; i < s.size(); i++) {  // 遍历一个字符串hash[s[i]]++;  // 把s的每个字符放进哈希表中}                  for (int i = 0; i < t.size(); i++) {hash[t[i]]--;  // 在hash表中抵消该字符次数if (hash[t[i]] < 0) {return false;}}return true;  // 若出现次数都一致，则返回true}
};

• 时间复杂度：O(n)。其中n为字符串的长度，需要遍历两个字符串，并对哈希表进行常数次操作。
• 空间复杂度：O(n)。因为哈希表中最多存储 n 个字符，所以空间复杂度与输入的字符串长度有关。