XingHuiSama の博客

Leetcode的100热题的第二题

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

示例 1:

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

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

解释：

在 strs 中没有字符串可以通过重新排列来形成 "bat"。
字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。
字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。

示例 2:

输入: strs = [""]

输出: [[""]]

示例 3:

输入: strs = ["a"]

输出: [["a"]]

提示：

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

解题思路：

这道题的核心是“特征提取”。我们不把庞大的字符串数组作为 Value 存在哈希表里，而是把哈希表当成一个“目录路由器”。

生成特征：统计每个单词 26 个字母的出现频率，拼接成带有 # 号分隔的字符串，作为唯一标识（Key）。
下标映射：哈希表的 Value 只存这个特征在结果数组 ans 中的真实下标。
动态分配：遇到见过的特征，直接通过哈希表拿到下标，精准投递；遇到新特征，在 ans 末尾开辟一个新组，并立刻把新下标 ans.size() - 1 登记到目录中。

class 字母异位词分组 {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        map<string,int> m;
        vector<vector<string>> ans;

        for (int i = 0;i < strs.size();i++) {
            auto item = strs[i];
            int arr[26] = {0};
            for (int j = 0;j < item.size();j++) {
                arr[item[j] - 'a']++;
            }
            string key = "";
            for (int j = 0;j < 26;j++) {
                key += to_string(arr[j]) + '#';
            }
            if (m.find(key) != m.end()) {
                ans[m[key]].push_back(item);
            }
            else {
                vector<string> temp;
                temp.push_back(item);
                ans.push_back(temp);
                m[key] = ans.size()-1;
            }
        }
        return ans;
    }
};

C++ 避坑备忘录

push_back 是纯动作，不产出物品：
- Java 的集合添加方法常常可以链式调用或者有返回值。
- C++ 的 push_back() 返回值是 void，它只负责把东西塞进去。如果你想把一个新元素直接包装成数组塞入二维数组，使用大括号 {item} 也就是 ans.push_back({item}) 是最简洁合法的。
下标错位的夺命坑：
- 在同时操作“遍历用”的数组（strs）和“收集用”的数组（ans）时，千万不要把原数组的 i 当成结果数组的下标。利用 ans.size() - 1 来获取最新分配的位置，是极其高明的手段。
不要轻信 C++ 的默认值：
- 在函数内部写 int arr[26];，里面装的全是不可预知的内存垃圾。必须要写成 int arr[26] = {0}; 才能安心使用。