Leetcode刷题 由浅入深之哈希表——242. 有效的字母异位词

目录

（一）字母异位词的C++实现

写法一（辅助数组）

（二）复杂度分析

时间复杂度

空间复杂度

（三）总结

---

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

给定两个字符串 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 仅包含小写字母

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

（一）字母异位词的C++实现

写法一（辅助数组）

解题思路：

        字母异位词的意思是两个词语中的字母和字母出现次数都是相同的，我们可以定义一个整型的辅助数组，用来存储每一个字母出现的次数。为了涵盖所有的测试样例，需要设置一个长度至少为26的数组并初始化为0。

        接着，分别遍历两个字符串中的字符，如果出现对应字母，对数组中的数值进行相应的修改。最后循环判断数组的每一个元素是否为0（在修改时一个字符串是＋1，另一个字符串是-1，因此当为零时说明两个字符串中都没有出现或者是都出现且数量相等）。

        在本题中，s 和 t 仅包含小写字母，因此，我们采用相对位置对数组进行访问即可。

class Solution {
public:bool isAnagram(string s, string t) {vector<int> list(26, 0);for(auto i : s)list[i-'a']++;    //i-'a' 采用相对位置对数组元素进行访问for(auto j : t)list[j-'a']--;for(auto k : list){if(k != 0)return false;}return true;}
};

（二）复杂度分析

时间复杂度

        整个算法的时间复杂度取决于字符串 s 和 t 的长度，总体时间复杂度为 。通常情况下，若两个字符串长度相等，设长度为 n，则时间复杂度可简化为 。

空间复杂度

        该算法使用了一个长度为 26 的 vector<int> 数组 list 来存储每个字母的出现次数。无论输入字符串的长度如何，这个数组的大小始终是固定的 26，不随输入规模的增大而增大。所以，空间复杂度为。

（三）总结

（1）辅助数组思想的应用，也就是哈希表。

（2）在本题中s 和 t 仅包含小写字母，可以尝试解决包含 unicode 字符该如何处理。

学习中，诚挚希望有心者指正和交流，经验或者方法都可。