力扣hot 100：49. 字母异位词分组(python & C++)

原题目链接

题目描述：

示例 1:

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
示例 2:

输入: strs = [“”]
输出: [[“”]]
示例 3:

输入: strs = [“a”]
输出: [[“a”]]

提示：

1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

题解（python）：（方法一：排序）

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        mp = collections.defaultdict(list)

        for st in strs:
            key = "".join(sorted(st))
            mp[key].append(st)

        return list(mp.values())
1
2
3
4
5
6
7
8
9

代码解析

这段代码定义了一个名为 Solution 的类，类中包含一个名为 groupAnagrams 的方法。该方法用于将一组字符串按字母异位词（anagram）分组。以下是代码的逐行解析：

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
1
2

• 这段代码定义了一个类 Solution，类中包含一个方法 groupAnagrams。这个方法接收一个参数 strs，它是一个字符串列表（List[str]），返回值是一个列表，列表中的每个元素也是一个字符串列表（List[List[str]]）。

        mp = collections.defaultdict(list)
1

• 这里定义了一个名为 mp 的变量，它是一个 defaultdict（来自 collections 模块）。defaultdict 是一种字典，它在引用的键不存在时会自动创建键，并将其值初始化为指定的默认值。在这个例子中，默认值是一个空列表。

        for st in strs:
            key = "".join(sorted(st))
            mp[key].append(st)
1
2
3

• 这一段代码遍历输入的字符串列表 strs。
  • 对于每个字符串 st，通过 sorted(st) 对字符串的字符进行排序，得到一个排序后的字符列表。
  • 然后通过 ''.join(sorted(st)) 将排序后的字符列表重新组合成一个字符串 key。
  • 使用这个 key 作为键，将原始字符串 st 添加到 mp 字典中对应的列表中。

        return list(mp.values())
1

• 最后，将字典 mp 中所有的值（即各个字母异位词分组的列表）转换为一个列表，并返回这个列表。

总结：

• 这个方法的主要作用是将输入的字符串列表按字母异位词分组。字母异位词是指由相同字母组成但顺序不同的字符串。
• 通过对每个字符串的字符进行排序，可以生成唯一的键（排序后的字符串），用这个键来将原始字符串分组。

例如，输入 ["eat", "tea", "tan", "ate", "nat", "bat"]，该方法将返回 [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]。

代码运行解析

当然可以！我们来详细跟踪代码执行的每一步，以理解它是如何处理输入 ["eat", "tea", "tan", "ate", "nat", "bat"] 的。

import collections

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        mp = collections.defaultdict(list)
1
2
3
4
5

• 创建了一个 defaultdict，初始状态 mp 是空的：mp = {}。

        for st in strs:
            key = "".join(sorted(st))
            mp[key].append(st)
1
2
3

遍历 strs 列表，并对每个字符串执行以下操作：

1. 处理 st = "eat":

   • sorted("eat") 结果是 ['a', 'e', 't']
   • key = "".join(['a', 'e', 't']) 结果是 "aet"
   • mp["aet"].append("eat")，更新后的 mp 是：{'aet': ['eat']}

2. 处理 st = "tea":

   • sorted("tea") 结果是 ['a', 'e', 't']
   • key = "".join(['a', 'e', 't']) 结果是 "aet"
   • mp["aet"].append("tea")，更新后的 mp 是：{'aet': ['eat', 'tea']}

3. 处理 st = "tan":

   • sorted("tan") 结果是 ['a', 'n', 't']
   • key = "".join(['a', 'n', 't']) 结果是 "ant"
   • mp["ant"].append("tan")，更新后的 mp 是：{'aet': ['eat', 'tea'], 'ant': ['tan']}

4. 处理 st = "ate":

   • sorted("ate") 结果是 ['a', 'e', 't']
   • key = "".join(['a', 'e', 't']) 结果是 "aet"
   • mp["aet"].append("ate")，更新后的 mp 是：{'aet': ['eat', 'tea', 'ate'], 'ant': ['tan']}

5. 处理 st = "nat":

   • sorted("nat") 结果是 ['a', 'n', 't']
   • key = "".join(['a', 'n', 't']) 结果是 "ant"
   • mp["ant"].append("nat")，更新后的 mp 是：{'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat']}

6. 处理 st = "bat":

   • sorted("bat") 结果是 ['a', 'b', 't']
   • key = "".join(['a', 'b', 't']) 结果是 "abt"
   • mp["abt"].append("bat")，更新后的 mp 是：{'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat'], 'abt': ['bat']}

        return list(mp.values())
1

• 最终，将 mp 的值转换为列表：list(mp.values())。
• 返回结果是 [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]。

综上，代码的每一步执行结果如下：

1. mp = {} （初始状态）
2. mp = {'aet': ['eat']}
3. mp = {'aet': ['eat', 'tea']}
4. mp = {'aet': ['eat', 'tea'], 'ant': ['tan']}
5. mp = {'aet': ['eat', 'tea', 'ate'], 'ant': ['tan']}
6. mp = {'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat']}
7. mp = {'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat'], 'abt': ['bat']}
8. 返回值：[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

题解（C++）：（方法一：排序）

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;
        for (string& str:strs){
            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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

代码解析&运行解析

这段代码定义了一个名为 Solution 的类，类中包含一个名为 groupAnagrams 的方法。这个方法用于将一组字符串按字母异位词（anagram）分组。以下是代码的逐行解析：

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
1
2
3

• 这段代码定义了一个类 Solution，类中包含一个公有方法 groupAnagrams。该方法接收一个引用参数 strs，它是一个字符串的向量（vector<string>），返回值是一个二维字符串向量（vector<vector<string>>）。

        unordered_map<string, vector<string>> mp;
1

• 这里定义了一个名为 mp 的变量，它是一个 unordered_map，键类型是 string，值类型是 vector<string>。这个哈希映射用于将排序后的字符串（作为键）映射到原始字符串列表（作为值）。

        for (string& str: strs) {
            string key = str;
            sort(key.begin(), key.end());
            mp[key].emplace_back(str);
        }
1
2
3
4
5

• 这一段代码遍历输入的字符串向量 strs。
  • 对于每个字符串 str，将其复制到 key 中。
  • 通过 sort(key.begin(), key.end()) 对 key 中的字符进行排序。
  • 使用排序后的 key 作为键，将原始字符串 str 添加到 mp 字典中对应的列表中。

        vector<vector<string>> ans;
1

• 创建一个空的二维字符串向量 ans，用于存储结果。

        for (auto it = mp.begin(); it != mp.end(); ++it) {
            ans.emplace_back(it->second);
        }
1
2
3

• 遍历 mp 中的每一个键值对。
  • 对于每一个键值对，将值（即一个字符串列表）添加到 ans 中。

        return ans;
    }
};
1
2
3

• 最后，返回 ans，它包含了按字母异位词分组的字符串列表。

总结：

• 这个方法的主要作用是将输入的字符串向量按字母异位词分组。字母异位词是指由相同字母组成但顺序不同的字符串。
• 通过对每个字符串的字符进行排序，可以生成唯一的键（排序后的字符串），用这个键来将原始字符串分组。

例如，输入 ["eat", "tea", "tan", "ate", "nat", "bat"]，该方法将返回 [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]。

让我们详细跟踪代码执行的每一步，以理解它是如何处理输入 ["eat", "tea", "tan", "ate", "nat", "bat"] 的。

假设输入是 ["eat", "tea", "tan", "ate", "nat", "bat"]，代码的每一步执行结果如下：

1. 创建 mp：mp = {}（初始状态）

2. 处理 str = "eat"：

   • key = "eat"
   • sort(key.begin(), key.end()) 结果是 key = "aet"
   • mp["aet"].emplace_back("eat")，更新后的 mp 是：{"aet": ["eat"]}

3. 处理 str = "tea"：

   • key = "tea"
   • sort(key.begin(), key.end()) 结果是 key = "aet"
   • mp["aet"].emplace_back("tea")，更新后的 mp 是：{"aet": ["eat", "tea"]}

4. 处理 str = "tan"：

   • key = "tan"
   • sort(key.begin(), key.end()) 结果是 key = "ant"
   • mp["ant"].emplace_back("tan")，更新后的 mp 是：{"aet": ["eat", "tea"], "ant": ["tan"]}

5. 处理 str = "ate"：

   • key = "ate"
   • sort(key.begin(), key.end()) 结果是 key = "aet"
   • mp["aet"].emplace_back("ate")，更新后的 mp 是：{"aet": ["eat", "tea", "ate"], "ant": ["tan"]}

6. 处理 str = "nat"：

   • key = "nat"
   • sort(key.begin(), key.end()) 结果是 key = "ant"
   • mp["ant"].emplace_back("nat")，更新后的 mp 是：{"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"]}

7. 处理 str = "bat"：

   • key = "bat"
   • sort(key.begin(), key.end()) 结果是 key = "abt"
   • mp["abt"].emplace_back("bat")，更新后的 mp 是：{"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"], "abt": ["bat"]}

遍历 mp，将每个值（字符串列表）添加到 ans 中：

• ans = [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

返回 ans，最终结果是：[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]。