本文主要是介绍leetcode242. 有效的字母异位词，哈希表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
leetcode242. 有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
示例 1:
输入: s = “anagram”, t = “nagaram”
输出: true
示例 2:
输入: s = “rat”, t = “car”
输出: false
提示:
1 <= s.length, t.length <= 5 * 104
s 和 t 仅包含小写字母
目录
- leetcode242. 有效的字母异位词
- 题目分析
- 算法步骤
- 算法流程
- 具体代码
- 算法分析
- 相似题目
题目分析
给定两个字符串 s 和 t，判断 t 是否是 s 的字母异位词。字母异位词是指由相同字母重排列形成的字符串。这个问题可以通过哈希表（或称为字典）来解决。
算法步骤
- 初始化一个无序哈希表
p。 - 遍历字符串
s，将每个字符的出现次数存储在哈希表中。 - 遍历字符串
t，减少哈希表中对应字符的出现次数。 - 遍历哈希表
p，检查每个字符的出现次数是否为0。 - 如果所有字符的出现次数都为0，则返回
true，表示t是s的字母异位词；否则返回false。
算法流程
具体代码
class Solution {
public:bool isAnagram(string s, string t) {unordered_map<char,int> p;for(int i=0;i<s.size();i++){p[s[i]]++;}for(int i=0;i<t.size();i++){p[t[i]]--;}for(auto q:p){if(q.second!=0) return false;}return true;}
};
算法分析
- 时间复杂度: O(n)，其中 n 是字符串
s和t的长度之和。 - 空间复杂度: O(1)，因为哈希表的大小只取决于字符集的大小，对于英文字母而言，其大小是固定的。
- 易错点: 在处理字符出现次数时，需要注意字符的ASCII值范围，确保所有字符都能被正确处理。
相似题目
| 题目 | 链接 |
|---|---|
| 242. 有效的字母异位词 | https://leetcode.cn/problems/valid-anagram/ |
| 49. 字母异位词分组 | https://leetcode.cn/problems/group-anagrams/ |
| 剑指 Offer II 032. 有效的变位词 | https://leetcode.cn/problems/dKk3P7/ |
这篇关于leetcode242. 有效的字母异位词，哈希表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
