LeetCode 242. 有效的字母异位词（C语言详解 | 哈希计数法）
一、题目描述
给定两个字符串s和t，编写一个函数来判断t 是否是 s 的字母异位词。
字母异位词（Anagram）指的是由相同字母重新排列形成的字符串。
示例
示例 1：
输入: s = "anagram", t = "nagaram" 输出: true示例 2：
输入: s = "rat", t = "car" 输出: false提示
1 <= s.length, t.length <= 5 * 10^4s和t仅包含小写字母
进阶：如果字符串包含Unicode 字符，应该如何处理？
二、解题思路
判断两个字符串是否为字母异位词，本质就是：
两个字符串中每个字符出现的次数必须完全相同。
例如：
s = anagram t = nagaram统计字符出现次数：
| 字符 | 次数 |
|---|---|
| a | 3 |
| n | 1 |
| g | 1 |
| r | 1 |
| m | 1 |
两个字符串统计结果完全一致，因此是字母异位词。
由于题目说明只包含小写字母 a-z，我们可以使用一个长度为 26 的数组来统计字符出现次数。
算法步骤
如果两个字符串长度不同，直接返回
false创建数组
count[26]遍历字符串
s，统计字符出现次数遍历字符串
t，减少对应字符次数如果最终数组全部为
0，说明字符数量完全一致
三、代码实现（C语言）
#include <stdbool.h> #include <string.h> bool isAnagram(char* s, char* t) { int len1 = strlen(s); int len2 = strlen(t); // 长度不同直接返回 if (len1 != len2) { return false; } int count[26] = {0}; // 统计字符次数 for (int i = 0; i < len1; i++) { count[s[i] - 'a']++; count[t[i] - 'a']--; } // 判断是否全部为0 for (int i = 0; i < 26; i++) { if (count[i] != 0) { return false; } } return true; }四、复杂度分析
| 类型 | 复杂度 |
|---|---|
| 时间复杂度 | O(n) |
| 空间复杂度 | O(1) |
说明：
只需要遍历一次字符串
使用固定大小
26的数组，因此空间复杂度为常数级
五、优化写法（推荐）
可以在同一次循环中同时进行加减操作，代码更加简洁。
#include <stdbool.h> #include <string.h> bool isAnagram(char* s, char* t) { if (strlen(s) != strlen(t)) return false; int count[26] = {0}; for (int i = 0; s[i] != '\0'; i++) { count[s[i] - 'a']++; count[t[i] - 'a']--; } for (int i = 0; i < 26; i++) { if (count[i] != 0) return false; } return true; }六、进阶问题：如果包含 Unicode 字符怎么办？
如果字符串包含Unicode 字符，字符集会非常大，此时无法使用26的数组。
可以采用：
方法：哈希表
思路：
使用哈希表统计
s中字符出现次数遍历
t，减少对应字符次数如果某个字符次数小于 0，则不是异位词
在 C 语言中可以：
使用uthash
或自己实现哈希表
时间复杂度仍然是：
O(n)七、总结
判断字母异位词的核心思想是：
统计字符出现次数是否完全一致。
常见解法：
1️⃣计数数组（推荐）
时间复杂度：O(n)
空间复杂度：O(1)
2️⃣排序比较
排序两个字符串后比较
时间复杂度：O(n log n)
在面试和算法题中，计数数组是最优解法。