怎么开一家客服外包公司_安徽建设厅官网_网络黄页推广大全_公司网站建站要多少钱

链接	有效的字母异位词
题序号	242
题型	字符串
解法	哈希表
难度	简单
熟练度	✅✅✅

题目

• 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

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

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

• 提示:
  1 <= s.length, t.length <= 5 * 10⁴
  s 和 t 仅包含小写字母

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

题解

1. 字母异位词：它们包含相同字符，并且每个字符出现的次数也相同。
2. 核心思想：使用哈希表来解决“有效的字母异位词”问题是一种非常直观和高效的方法。基本思路是通过哈希表来记录每个字符的出现次数，然后比较两个字符串的字符计数是否相同。
3. 复杂度：时间复杂度O(n)，空间复杂度O(1)。
4. c++ 实现算法：

bool isAnagram(string s, string t) {if (s.length() != t.length()) return false; // 长度不同直接返回 falseunordered_map<char, int> count;for (char c : s) count[c]++; // 统计 s 中每个字符的出现次数for (char c : t) {if (count[c] == 0) return false; // 如果字符 c 的计数为 0，说明 t 多出字符count[c]--; // 减少对应字符的计数}return true;
}

4. 算法推演：

1. 输入及初始化
   string s = “anagram”; string t = “nagaram”;

• 检查长度：
  if (s.length() != t.length()) return false; s.length() =7，t.length() = 7，长度相等，继续执行。
• 初始化哈希表：
  unordered_map<char, int> count; 创建一个空的哈希表 count，用于存储 s 中每个字符的频率。

2. 遍历字符串 s，统计字符频率
   for (char c : s) count[c]++;
   遍历字符串 s = “anagram”：
   遇到 ‘a’，count[‘a’] = 1
   遇到 ‘n’，count[‘n’] = 1
   遇到 ‘a’，count[‘a’] = 2
   遇到’g’，count[‘g’] = 1
   遇到 ‘r’，count[‘r’] = 1
   遇到 ‘a’，count[‘a’] = 3
   遇到’m’，count[‘m’] = 1

• 最终哈希表状态： count = {
  ‘a’: 3,
  ‘n’: 1,
  ‘g’: 1,
  ‘r’: 1,
  ‘m’: 1 }

3. 遍历字符串 t，验证字符频率
   for (char c : t) {
   if (count[c] == 0) return false;
   count[c]–;
   }
   遍历字符串 t = “nagaram”，逐步验证 t 中的字符是否匹配：

• 第 1 个字符 ‘n’：
  检查 count[‘n’]，当前值为 1（非 0）。 将 count[‘n’]–，更新为 0。
  哈希表状态：
  count = {
  ‘a’: 3,
  ‘n’: 0,
  ‘g’: 1,
  ‘r’: 1,
  ‘m’: 1 }

• 第 2 个字符 ‘a’：
  检查 count[‘a’]，当前值为 3（非 0）。 将 count[‘a’]–，更新为 2。
  哈希表状态：
  count = {
  ‘a’: 2,
  ‘n’: 0,
  ‘g’: 1,
  ‘r’: 1,
  ‘m’: 1 }

• 第 3 个字符 ‘g’： 检查 count[‘g’]，当前值为 1（非 0）。 将 count[‘g’]–，更新为 0。
  哈希表状态：
  count = {
  ‘a’: 2,
  ‘n’: 0,
  ‘g’: 0,
  ‘r’: 1,
  ‘m’: 1 }

• 第 4 个字符 ‘a’： 检查 count[‘a’]，当前值为 2（非 0）。 将 count[‘a’]–，更新为 1。
  哈希表状态：
  count = {
  ‘a’: 1,
  ‘n’: 0,
  ‘g’: 0,
  ‘r’: 1,
  ‘m’: 1 }

• 第 5 个字符 ‘r’： 检查 count[‘r’]，当前值为 1（非 0）。 将 count[‘r’]–，更新为 0。
  哈希表状态：
  count = {
  ‘a’: 1,
  ‘n’: 0,
  ‘g’: 0,
  ‘r’: 0,
  ‘m’: 1 }

• 第 6 个字符 ‘a’： 检查 count[‘a’]，当前值为 1（非 0）。 将 count[‘a’]–，更新为 0。
  哈希表状态：
  count = {
  ‘a’: 0,
  ‘n’: 0,
  ‘g’: 0,
  ‘r’: 0,
  ‘m’: 1 }

• 第 7 个字符 ‘m’： 检查 count[‘m’]，当前值为 1（非 0）。 将 count[‘m’]–，更新为 0。
  哈希表状态：
  count = {
  ‘a’: 0,
  ‘n’: 0,
  ‘g’: 0,
  ‘r’: 0,
  ‘m’: 0 }

4. 验证完成 遍历字符串 t 的所有字符后，未提前返回 false。 哈希表中所有字符的计数均为 0，说明 s 和 t 是字母异位词。

5. 返回结果 return true; 输出结果为 true，即 s = “anagram” 和 t = “nagaram” 是字母异位词。

5. c++ 完整 demo：

#include <iostream>
#include <unordered_map>
using namespace std;bool isAnagram(string s, string t) {if (s.length() != t.length()) return false; // 长度不同直接返回 falseunordered_map<char, int> count;for (char c : s) count[c]++; // 统计 s 中每个字符的出现次数for (char c : t) {if (count[c] == 0) return false; // 如果字符 c 的计数为 0，说明 t 多出字符count[c]--; // 减少对应字符的计数}return true;
}int main() {string s = "anagram";string t = "nagaram";cout << (isAnagram(s, t) ? "True" : "False") << endl;return 0;
}