【LeetCode 刷题日志】哈希表经典双题：242. 有效的字母异位词 & 49. 字母异位词分组（C++ 详解）

【LeetCode 刷题日志】哈希表经典双题：242. 有效的字母异位词 & 49. 字母异位词分组（C++ 详解）

本文是我的 LeetCode 刷题日志系列之一，用 C++ 语言深入讲解两道经典的哈希表题目 ——

242. 有效的字母异位词

和

49. 字母异位词分组

。这两题一脉相承，是面试高频题，也是掌握哈希表思想的绝佳入门组合。文章包含完整的题目描述、多种解题思路、C++ 代码实现、复杂度分析、踩坑记录和学习感悟，

适合算法新手和有一定基础想要巩固哈希表的同学

阅读。

📑 本文目录

• 一、力扣 242. 有效的字母异位词
• 二、力扣 49. 字母异位词分组
• 三、两题关联与进阶思考
• 四、刷题心得与学习感悟
• 五、总结

📋 本篇日志包含的题目

💡

为什么把这两题放在一起？

第 242 题是判断两个字符串是否为字母异位词，第 49 题是将一组字符串中的字母异位词分组。后者是前者的进阶和推广，掌握了 242 的核心思想，49 就水到渠成。

一、力扣 242. 有效的字母异位词

1.1 题目描述

给定两个字符串 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 * 10^4

• s 和 t 仅包含小写字母

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

1.2 解题思路

思路一：排序法（最直观）

核心思想： 如果两个字符串是字母异位词，那么把它们排序后得到的字符串一定完全相同。

步骤：

优点： 思路简单，代码短，容易想到缺点： 排序的时间复杂度较高，为 O(n log n)n)

思路二：哈希表计数法（最优解）

核心思想： 题目明确说明只包含小写字母，共 26 个，因此可以用一个长度为 26 的数组来模拟哈希表，统计每个字符出现的次数。

步骤：

优化技巧： 在遍历 t 的过程中，如果某个位置减到负数，可以提前返回 false，减少不必要的遍历。

1.3 C++ 代码实现

方法一：排序法

class Solution {
public:
bool isAnagram(string s, string t) {
// 长度不同直接返回false
if (s.length() != t.length()) {
return false;
}
// 排序后比较
sort(s.begin(), s.end());
sort(t.begin(), t.end());
return s == t;
}
};

方法二：数组计数法（推荐）

class Solution {
public:
bool isAnagram(string s, string t) {
if (s.length() != t.length()) {
return false;
}
vector<int> table(26, 0);
for (auto& ch: s) {
table[ch – 'a']++;
}
for (auto& ch: t) {
table[ch – 'a']—;
if (table[ch – 'a'] < 0) {
return false;
}
}
return true;
}
};

1.4 复杂度分析

其中 n 为字符串长度。

1.5 踩坑记录与注意点

二、力扣 49. 字母异位词分组

2.1 题目描述

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

字母异位词指字母相同，但排列不同的字符串。

示例 1：

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2：

输入: strs = [""]

输出: [[""]]

示例 3：

输入: strs = ["a"]

输出: [["a"]]

提示：

• 1 <= strs.length <= 10^4

• 0 <= strs[i].length <= 100

• strs[i] 仅包含小写字母

2.2 解题思路

思路一：排序 + 哈希表（最常用）

核心思想： 互为字母异位词的字符串，排序后的结果相同。因此可以将排序后的字符串作为哈希表的 key，原始字符串作为 value 存入对应的列表中。

步骤：

• 对字符串进行排序，得到 key

• 将原始字符串添加到哈希表中 key 对应的 vector 中

思路二：字符计数编码 + 哈希表（优化版）核心思想： 排序的时间复杂度是 O(k log k)（k 为字符串长度），我们可以用计数的方式生成一个唯一的编码作为 key，时间复杂度降为 O(k)。)。

编码方式： 由于只有 26 个小写字母，我们可以统计每个字符出现的次数，然后用一种分隔符（如 #）拼接成一个字符串作为 key。例如 "aab" 的计数是 a:2, b:1，编码为 "2#1#0#0#…#0"（共 26 个数字，用 # 分隔）。）。

步骤：

• 统计 26 个字母各自出现的次数

• 将计数数组编码成唯一字符串作为 key

• 将原始字符串加入对应列表

2.3 C++ 代码实现

方法一：排序 + 哈希表

class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> mp;
for (string& str: strs) {
// 排序后的字符串作为key
string key = str;
sort(key.begin(), key.end());
mp[key].emplace_back(str);
}
// 收集结果
vector<vector<string>> ans;
for (auto it = mp.begin(); it != mp.end(); ++it) {
ans.emplace_back(it->second);
}
return ans;
}
};

方法二：利用 C++17 结构化绑定简化代码

class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> mp;

for (auto& str : strs) {
string key = str;
sort(key.begin(), key.end());
mp[key].push_back(str);
}

vector<vector<string>> result;
// C++17结构化绑定
for (auto& [key, group] : mp) {
result.push_back(move(group)); // 使用move避免拷贝
}

return result;
}
};

2.4 复杂度分析

设 n 为字符串数组的长度，k 为每个字符串的最大长度。

说明：

• 排序法中，每个字符串排序需要 O (k log k)，共 n 个字符串

• 空间上，哈希表需要存储所有字符串，为 O (n × k)

2.5 踩坑记录与注意点

三、两题关联与进阶思考

3.1 从 242 到 49 的思维跃迁

思维提炼： 242 题中我们用计数数组判断两个字符串是否匹配；49 题中，我们需要把 “匹配” 这个关系推广到一组字符串中，自然就想到用哈希表把相同特征的字符串归到一起。这就是从 “两两比较” 到 “按特征分组” 的思维升级。

3.2 可复用模板汇总（其他题目直接套用）

这两道题虽然表面不同，但提炼出的模板可以复用到大量同类题目中。以下是从本题中总结的 4 个固定模板，每个模板给出代码、适用场景和可直接套用的题目。

模板一：字符计数数组模板（源自 242 题）

核心思想： 当字符集范围有限且较小时（如小写字母 26 个、ASCII 128 个），用数组代替 unordered_map 进行计数，效率更高。

// 模板：字符频率计数
// 适用：仅含小写字母 / 大写字母 / ASCII字符 的字符串统计问题
vector<int> countChars(const string& s) {
vector<int> count(26, 0); // 26个小写字母；大写字母用26，ASCII用128
for (char c : s) {
count[c – 'a']++; // 小写字母偏移；大写字母用 c – 'A'
}
return count;
}

// 模板：两个字符串计数比较（判断是否互为异位词/变位词）
bool compareCount(const string& s, const string& t) {
if (s.length() != t.length()) return false; // 长度剪枝
int count[26] = {0};
for (char c : s) count[c – 'a']++;
for (char c : t) {
count[c – 'a']—;
if (count[c – 'a'] < 0) return false; // 提前剪枝
}
return true;
}

适用场景：

• 字符频率统计与比较
• 判断两个字符串是否为异位词 / 变位词
• 找字符串中第一个不重复的字符
• 赎金信（字符串能否由另一个字符串构造）

可直接套用的题目：

模板二：哈希表特征分组模板（源自 49 题）

核心思想： 对于一组元素，提取每个元素的"特征"作为哈希表的 key，将相同特征的元素归为一组。这是分组类问题的通用解法。

// 模板：按特征分组
// 适用：需要将一组元素按某种共同特征归类的问题
template<typename T, typename KeyType>
vector<vector<T>> groupByFeature(const vector<T>& items,
function<KeyType(const T&)> extractFeature) {
unordered_map<KeyType, vector<T>> mp;
for (const T& item : items) {
KeyType key = extractFeature(item); // 提取特征作为key
mp[key].push_back(item);
}
vector<vector<T>> result;
for (auto& [key, group] : mp) {
result.push_back(move(group));
}
return result;
}

适用场景：

• 将一组元素按共同特征分组
• 查找重复元素（分组后组大小 > 1）
• 统计每组的数量 / 最大值 / 最小值

可直接套用的题目：

模板三：排序作 Key 模板（源自 49 题方法一）

核心思想： 当元素的"内容"相同但"顺序"不同时，排序后得到的结果相同，可以作为哈希表的 key。这是最简洁的特征提取方式。

// 模板：排序后作为key进行分组
// 适用：顺序无关、内容相同的元素分组
vector<vector<string>> groupBySort(const vector<string>& strs) {
unordered_map<string, vector<string>> mp;
for (const string& s : strs) {
string key = s;
sort(key.begin(), key.end()); // 排序后作为key
mp[key].push_back(s);
}
vector<vector<string>> result;
for (auto& [key, group] : mp) {
result.push_back(move(group));
}
return result;
}

适用场景：

• 字母异位词分组
• 变位词 / 相同字母组合的归类
• 数组中元素相同但排列不同的分组

优缺点：

• 代码极简，不容易出错
• 适用于任何可排序的元素类型
• 时间复杂度含排序因子 O(k log k)，k 为元素长度
• 要求元素可排序（字符串、数组等可以，自定义结构需定义比较函数）

可直接套用的题目： 49 题、249 题（需转换后排序）、面试题 10.02（变位词组）

模板选择速查表

实战建议： 面试中如果字符串长度 k <= 100，排序法（模板三）代码短、不易出错，是首选。两个字符串比较的场景永远用模板一。

四、刷题心得与学习感悟

4.1 这两题能学到什么？

4.2 新手常见误区

1暴力解法思维：新手做 49 题时容易想到两两比较（O(n² × k)），这在 n=10^4 时会超时。要建立 “用哈希表分组” 的意识。识。

4.3 我的刷题方法分享

五、总结

本文详细讲解了 LeetCode 242（有效的字母异位词）和 49（字母异位词分组）两道经典题目：

242 题：核心是用数组计数比较两个字符串的字符频率，时间 O(n)，空间 O(1)，是哈希表思想的基础应用。用。

• 49 题：核心是提取每个字符串的特征（排序结果或计数编码）作为哈希表的 key 进行分组，时间 O (n×k) 或 O (n×k log k)，是哈希分组思想的典型应用。

• 两题关系：49 题是 242 题的推广，从 “判断两个” 升级为 “分组多个”，体现了哈希表从比较到分组的思维跃迁。

这两道题是面试高频题，也是掌握哈希表的必刷题。希望这篇日志能帮助你理解其中的思想，也欢迎在评论区交流你的解法和心得！

下一篇预告

：继续哈希表专题，将讲解【283.移动零】和【11.盛最多水的容器】，敬请期待！ 如果本文对你有帮助，欢迎点赞 👍、收藏 ⭐、关注我，一起在算法之路上进步！