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

2025/4/19 18:24:58 来源：https://blog.csdn.net/m0_57082284/article/details/147314507 浏览: 次关键词：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;}
};