题目内容

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例

输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出:
[
[“ate”,”eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]

提示

1、所有输入均为小写字母。
2、不考虑答案输出的顺序。

题解

由于题目中给出的单词都是小写字母，因此可以通过将其中的元素全部调整为按照某种规律排布的方式统一化就可以求出字母异位词了。

这里，我们将出现的单词均作出从小到大的排布处理。将排好序的字符串作为key，然后将原字符串插入key对应的vector中。

这里我们可以采用hash表来进行映射存储。

时间复杂度分析：

假设N为字符串个数，L是每个单词的平均长度，hash表和vector插入操作的复杂度都是O(1)，排序复杂度是O(LlogL)，因此总的时间复杂度为：O(NLlogL)。

代码

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));//string存储字符串时内部有一个char*数组，那么在push_back时如果不使用move，那么会在vector的下一个位置新建一个char*数组，然后把原字符串复制过去；如果使用了move，那么vector的下一个位置里的char*就直接把原字符串的指针拿过来了，不需要复制整个字符串。这里就是为了减少依次拷贝操作。
        }

        vector<vector<string>> res;
        for (auto i = dict.begin(); i != dict.end(); i ++ )
        {
            res.push_back(move(i -> second));
        }

        return res;
    }
};