题目描述
给定一组字符串，将所有字母顺序颠倒的字符串归为一组。
注意：
- 所有输入均是小写字母
- 输出顺序随意
样例
输入：
["eat", "tea", "tan", "ate", "nat", "bat"]
输出：
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
算法
(哈希表) $O(NLlogL)$
定义从string 映射到 vector<string>的哈希表：unordered_map<string, vector<string>>，哈希表用法参见 这里 。
我们将每个字符串的所有字符从小到大排序，将排好序的字符串作为key，然后将原字符串插入key对应的vector<string>中。
时间复杂度分析：$N$ 是字符串个数，$L$ 是字符串平均长度。对于每个字符串，哈希表和vector的插入操作复杂度都是 $O(1)$，排序复杂度是 $O(LlogL)$。所以总时间复杂度是 $O(NLlogL)$。
C++ 代码
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> dict;
for (auto &str : strs)
{
string key = str;
sort(key.begin(), key.end());
dict[key].push_back(move(str));
}
vector<vector<string>> res;
for (auto i = dict.begin(); i != dict.end(); i ++ )
{
res.push_back(move(i -> second));
}
return res;
}
};
其实
dict[key].push_back(str)写成dict[key].push_back(move(str))更好，直接移动str，减少一次拷贝。同理最后
res.push_back(i -> second)也可以写成res.push_back(move(i -> second))，减少拷贝。这样，
strs中的字符串只会在key这里进行一次拷贝，其余均为移动。不错啊。已修改~
move是什么意思？
本来需要将整个字符串copy过去，使用move之后只需要把字符串的首地址赋值过去，可以减少一次拷贝操作，提高效率。
谢谢y佬
h
这个版本最精简，威武
谢谢hh
move是把右值赋给左值，但不创建新空间吗
内部的逻辑是这样的：
string存储字符串时内部有一个char*数组，那么在push_back时如果不使用move，那么会在vector的下一个位置新建一个char*数组，然后把原字符串复制过去；如果使用了move，那么vector的下一个位置里的char*就直接把原字符串的指针拿过来了，不需要复制整个字符串。秒懂，感谢y总
for(auto &str : strs)加上const感觉更舒服点
看个人习惯吧hh 算法题的代码都比较短，写得会随意一些
请问第二个for循环里的迭代器，写成for (auto i = dict.begin(); i != dict.end(); i ++ )
{
res.push_back(i -> second);
}
迭代器i就当做指针，使用->操作符。但如果按照题解视频里的使用基于范围的for循环：
for(auto group : hash){
res.push_back(group.second);
}
迭代器又变成对象了，使用.操作符，这是为什么呢？
在第一个循环里
i是dict的迭代器，用法类似于指针，用i->second索引；在第二个循环里i是dict里的某个元素，直接用group.second索引就可以。谢谢灿大，我搞错了。
么事hh
排序复杂度不应该是O(Llog(L))吗，总复杂度不是O(NLlog(L))吗，另外排序可以换成单词频次的hash表，此时复杂度是O(NL)
笔误hh，已更正。
照着这个思路，实现了一个时间复杂度O(NL)的算法，链接
棒！
如果字符串很长的话，哈希表的key可以使用不同字符出现的次数如“1_2_3_…”代表字符串有一个a两个b3个c之类的。然后map的value不用存储字符串，而是存储字符串在strs数组中的下标，好像也可以？
感觉这种group题就是都是需要找到一个比较方便的hash表示。
可以的。对滴~
好像可以去掉if (dict.count(key) == 0) dict[key] = vector[HTML_REMOVED](); 因为无论是否count（key）==0，都要push_back(str)
刚刚试了一下，确实可以去掉哈哈。已去除。
我一开始担心
unordered_map<string, vector<string>>不初始化的话，会崩溃，看来它会将所有第一次用的节点自动初始化成vector<string>()。