Leetcode第二题：用 C++ 解决字母异位词分组

1. 题目描述

先简要介绍一下题目。

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

通俗点讲，如果两个单词用的字母种类和数量完全一样，只是顺序打乱了，那么这两个单词就是字母异位词。

Leetcode 中给出的示例如下：

2. 解题思路

按照一般的解题思路，我们要把一些单词归位一类，首先要观察出这些单词的共同点。显然，他们的共同点就是组成这些单词的字母种类和每种字母的数量都相同。

了解了这个共同点之后，我们试想一下，如果把一组字母异位词按照字母 a~z 的先后顺序进行排序，那么这一组单词排序后得到的结果是相同的。

结合我们上一题学到的哈希表，解法思路如下：

1. 先建立一个哈希表。
2. 遍历这个字符串数组，把数组中的每个单词都重新排序得到它的标识。
3. 把这个标识作为哈希表的键key，把原本的单词作为哈希表的值value。这里不能颠倒，因为键是唯一的，插入重复的键会覆盖掉旧的。
4. 因为可能有多个单词对应同一个标识，所以这个哈希表的值应该是个数组。
5. 最后，把哈希表中所有的值提取出来，返回即可。

3. 具体代码实现

有了思路，下面我们来写代码：

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        //定义哈希表，哈希表的值是一个字符串数组
        unordered_map<string,vector<string>> hash;
        //遍历字符串数组的所有单词
        for(string &str : strs)
        {
            string key = str;//先把原单词拷贝一份用于重新排序
            sort(key.begin(),key.end());//进行排序，这个函数下面会讲
            hash[key].push_back(std::move(str));//把原单词放到对应标识的数组中
        }
        //把哈希表的值提取出来
        vector<vector<string>> result;
        result.reserve(hash.size());
        for(auto &pair : hash)
        {
            //pair.second指的就是哈希表的值
            result.push_back(std::move(pair.second));
        }
        return result;
    }
};

4. C++知识点详解

4.1 容器嵌套

在 C 语言中我们用 char** 或 char arr[][] 来表示字符串数组。

在 C++ 里，vector<string> 是一维字符串数组，那么 vector<vector<string>> 就是一个大数组里套着一个个小数组，即二维数组，正好对应题目要求的返回值格式：[["bat"], ["nat","tan"], ...]。

上一题我们的哈希表是<int, int>，这道题变成了 <string, vector<string>>。这展现了 C++ 泛型编程的强大，哈希表里不仅能存数字，还能存复杂的对象。

容器嵌套的关键在于：外层容器只负责存储内层容器的“管理对象”（句柄），而不直接存储内层容器的数据。

外层容器：在内存中连续或不连续地存放内层容器的控制结构。

内层容器：各自在堆上申请独立的内存空间。

当我们执行类似hash[key].push_back(str)这样的语句时，会触发内层容器的深拷贝，从而导致运行效率变差，我们可以使用 std::move 或 emplace_back来优化，正如上面代码实现中的做法那样。

4.2 范围for循环

之前，遍历数组我们都写 for(int i=0; i<strs.size(); i++)。在这道题里，采用了一种全新的写法：

for (string& str : strs) { ... }

含义是：对于 strs 这个容器里的每一个元素，我们依次把它拿出来，并将其命名为 str。

我们在 string& str 加了引用符号，是上一题中讲过的引用传递，这意味着我们是直接操作原数组里的字符串，而不是复制一份。如果字符串很长，不加 & 每次循环都会产生大量的拷贝开销，加上 & 性能会好很多。

4.3 标准排序算法

C++ 提供了一个极其强大的排序函数 sort，包含在 <algorithm> 头文件中。

sort(key.begin(), key.end());//默认升序排序

key.begin() 和 key.end() 返回的是字符串的起始迭代器和终止迭代器，key.begin() 指向第一个元素，key.end() 指向最后一个元素的下一个位置，这是一个左闭右开区间。

std::sort 并不是简单的快速排序，而是一种混合算法：初始阶段使用快速排序，平均速度最快。当递归深度达到一定阈值时，切换到堆排序。当数据量非常小时，切换到插入排序，利用其在小规模数据下的低常数开销。

sort 接受的是随机访问迭代器。支持的容器有：std::vector，std::deque， std::array以及原生数组。不支持的容器有：std::list 和 std::forward_list，因为他们不支持随机访问。

sort最强大的地方在于它可以自定义排序方式。我们可以通过 Lambda 表达式 或 谓词函数 改变排序逻辑，示例如下：

//降序排列
std::vector<int> v = {1, 3, 2};
std::sort(v.begin(), v.end(), [](int a, int b) {
    return a > b; // 如果 a > b，则 a 应该排在 b 前面
});

//结构体按照特定成员排序
struct Student {
    std::string name;
    int score;
};
​
std::vector<Student> students = {{"AAA", 90}, {"BBB", 85}};
​
// 按分数从高到低排序
std::sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
    return a.score > b.score; 
});

在自定义排序方式时，我们应该始终使用>或者<，如果带着=会导致sort 在元素相等时持续查找边界。

4.4 auto关键字

在最后提取结果的循环中，我们写了下面代码：

for (auto& pair : hash)

遍历哈希表时，每次拿出来的是一个键值对。在 C++ 中，它的标准类型极其冗长，叫做 std::pair<const std::string, std::vector<std::string>>。

如果要手写这么长的类型名，那实在是过于麻烦，所以 C++11 引入了 auto 关键字。auto 的作用是：让编译器自己去猜它到底是什么类型。 编译器知道我们此刻正在遍历哈希表，自动就把 pair 当作正确的键值对类型了。

在这个 pair 中，pair.first 就是键，pair.second 就是值，所以我们直接把 pair.second 放进 result 里即可。

4.5 预分配内存

上面代码中我们在定义好result之后，写了这样一行代码：

result.reserve(hash.size());

首先我们要知道std::vector中有两个关键属性：size和capacity。size是容器当前实际包含的元素个数，capacity是容器在不重新分配内存的情况下，最多能容纳的元素个数。

当我们不使用 reserve 时，当我们不断的 push_back 元素，一旦 size 超过了 capacity，vector 就会执行以下耗时的步骤：

1. 在内存中找一块更大的新空间。
2. 将旧空间的所有元素拷贝或移动到新空间。
3. 释放旧内存空间。

为了避免这样耗时的操作，我们使用了result.reserve(hash.size()) ，这行代码直接告诉编译器：“我能确定 result 最终至少要装下和 hash 一样多的数据，直接分配好这么大的空间。”

这样，就不会因为size超过capacity导致频繁的重新分配内存了。

4.6 std::move 的精髓

我们在代码中用到了std::move(str) 和 std::move(pair.second)，下面我们通过与常规情况下对比来理解std::move的作用。

假如我们的代码是push_back(str)，由于 str 还要继续存在，系统必须在 vector 里完整克隆一份字符串，这就是额外的开销。

而如果我们使用push_back(std::move(str))，vector 直接接管 str 指向的内存地址，原 str 变为空字符串，开销几乎为零。

但是还有一点需要提一下，既然已经把 str move 走了，它正处于合法但未定义的状态，那之后就不应该在访问str了。

这里，可能有人会这样想，在第一个for循环中（第二个for循环同理），for循环的运转是依赖str的，而我们在循环体内部却把str给move掉了，这难道不会导致程序异常吗？答案是完全不会。

当执行 hash[key].push_back(std::move(str)) 时，只是把 strs 数组里当前那个位置的字符串内容掏空搬到了别的地方，但这个位置本身（它的地址）本身依然存在，下一轮for循环时，这个位置又会装上新的内容。

5. 键与值的深度辨析

在处理复杂嵌套时，清晰的理解键和值的作用是解决问题的关键所在。

在本题中，键和值的特征如下：

5.1 键

类型为std::string。

内容为经过排序后的单词标识。

哈希表中的键必须是唯一的。每个唯一的键代表了一组互为字母异位词的集合。

5.2 值

类型为std::vector<std::string>。

内容为所有属于该分类的原始单词组成的数组。

同一个键可以对应多个值，每当发现一个新的单词，其排序后的 key 命中哈希表，我们就把原单词 push_back 到对应的 vector 中。

5.3 辨析

以后再使用哈希表时，一定要在内心问自己下面三个问题：

1. 这次使用哈希表的目的是什么？是查找还是分类？
2. 我要使用哪个东西来访问哈希表，map[?] 方括号里放的是什么？这个通常就是键。
3. 最终我得到了什么东西？map[key] 得到的是值，map[key].push_back(东西) 里的东西也是值。

按照题目的思路，我们可以把这三个问题套用在这道题上面。

1. 目的是把单词按是否异位词进行分组。
2. 用排序后的字符串去访问哈希表，这就是键。
3. 我们最终要查找的是原始单词的集合，这就是值。

本文结束