当前位置：首页 > ops >正文

05.字母异位词分组

ops 2025/6/28 18:16:37

在这里插入图片描述

题意理解

🧠 什么是“字母异位词”？

字母异位词是指由相同的字母组成，只是排列顺序不同的单词。

比如：

"eat" 和 "tea" 是异位词，它们都包含 'e'、'a' 和 't'。"ate" 也是它们的异位词。但是 "tan" 就不是，它包含 't'、'a'、'n'，和上面三个字母不同。

✅ 方法一：排序作为哈希表 key

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, vector<string>> mp;for (const string& str : strs){string key = str;sort(key.begin(), key.end()); // 将字符串排序，作为哈希表 keymp[key].push_back(str);       // 将原字符串加入对应分组}vector<vector<string>> res;for (const auto& [key, group] : mp) {res.push_back(group);         // 提取所有 value 即为分组结果}return res;}
};

🔍 时间复杂度

排序每个字符串 O(k log k)，总共 n 个字符串 ⇒ O(nk log k)

💾 空间复杂度

需要额外存储 HashMap 和结果集 ⇒ O(nk)

✅ 方法二：计数字符频率作为 key

class Solution 
{
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, vector<string>> mp;for (string& str : strs) {vector<int> count(26, 0);for (char ch : str) {count[ch - 'a']++;}// 手动编码计数数组，例如 "aabbc" → "a2b2c1"string key;for (int i = 0; i < 26; ++i) {if (count[i] > 0) {key += (char)('a' + i);key += to_string(count[i]);}}mp[key].push_back(str);}vector<vector<string>> res;for (auto& [key, group] : mp) {res.push_back(group);}return res;}
};