13 字母异位词分组

13 字母异位词分组

13.1 字母异位词分组解决方案

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        std::unordered_map<std::string, std::vector<std::string>> anagramMap;
        
        // 遍历输入字符串数组
        for (const std::string& word : strs) {
            std::string sortedWord = word; //先拷贝一份字符串，保留原单词不变
            std::sort(sortedWord.begin(), sortedWord.end()); // 将字符按字典顺序排列。字母异位词将会得到相同的排序结果。
            anagramMap[sortedWord].push_back(word); // 将使用排序后的字符串sortedWord作为键，将word添加到哈希表 anagramMap 中对应的键的向量中。
        }
        
        std::vector<std::vector<std::string>> result;
        for (const auto& entry : anagramMap) {
            result.push_back(entry.second);
        }
        
        return result;
    }
};

基本思路：将字母异位词按照字母排序后得到一个唯一的“标准形式”，并将所有拥有相同“标准形式”的单词分到同一个组中。

代码解析：

1. 定义字典 anagramMap:
   1. anagramMap 是一个哈希表，用于存储字母异位词组。
   2. 字典的键是每个单词排序后的形式（即按字母排序得到的“标准形式”）。
   3. 字典的值是一个字符串列表，包含了所有和这个标准形式匹配的字母异位词。
2. 遍历输入的字符串数组 strs:
   1. for (const std::string& word : strs)：遍历 strs 中的每个单词 word。
   2. std::string sortedWord = word;：将当前单词复制到 sortedWord 中，保留原始单词不变，以便之后添加到分组中。
   3. std::sort(sortedWord.begin(), sortedWord.end());：将 sortedWord 的字符按字典顺序排序。排序后，所有字母异位词将会得到相同的排序结果。例如，“eat” 和 “tea” 排序后都变成 “aet”。
   4. anagramMap[sortedWord].push_back(word);：使用排序后的字符串 sortedWord 作为键，将 word 添加到字典 anagramMap 中对应的向量（值）中。这一步的效果是将所有字母异位词（即排序后相同的单词）分配到同一个组中。
3. 收集结果：
   1. 定义一个二维向量 result，用于存储最终的分组结果。
   2. for (const auto& entry : anagramMap)：遍历 anagramMap 中的每个键值对 entry。
      1. entry.first 是排序后的单词（作为键）。
      2. entry.second 是与该键对应的字母异位词列表（即值）。
   3. result.push_back(entry.second);：将 entry.second（一个字母异位词组）添加到 result 中。
4. 返回结果：
   1. 返回 result，其中包含了所有的字母异位词分组。

时间复杂度：该算法的时间复杂度为 $O(N\times KlogK)$，其中 N 是单词数量，K 是单词的平均长度。
空间复杂度：额外的空间复杂度取决于输入数据，因为 anagramMap 和 result 都需要额外的存储空间。

13.2 举例说明

假设我们有一个输入字符串数组：

strs = {"eat", "tea", "tan", "ate", "nat", "bat"};

代码的工作流程如下：

1. 初始化哈希表 anagramMap：

• 用来存储相同字母异位词的分组。键是排序后的字符串（每组字母异位词都会有相同的排序结果），值是原始字符串的向量，用于存储属于同一组的字母异位词。

2. 遍历字符串数组 strs：

• 对于每个字符串，生成它的排序版本，作为在 anagramMap 中的键。

• 然后将原始字符串加入到对应的键所表示的向量中。
  详细过程：

• 先处理字符串 “eat”：

  • 排序后得到 “aet”。
  • 在 anagramMap 中，将 “eat” 添加到键 “aet” 对应的向量中。

• 处理字符串 “tea”：

  • 排序后也是 “aet”。
  • 将 “tea” 添加到键 “aet” 对应的向量中。

• 处理字符串 “tan”：

  • 排序后得到 “ant”。
  • 将 “tan” 添加到键 “ant” 对应的向量中。

• 依次处理 “ate”（排序后 “aet”，加入键 “aet”）、“nat”（排序后 “ant”，加入键 “ant”）、“bat”（排序后 “abt”，加入键 “abt”）。
  构造结果：

• 遍历 anagramMap，将每个键对应的向量加入到结果 result 中。

• 最终得到的结果是按字母异位词分组的二维向量。