49. Group Anagrams

Given an array of strings, group anagrams together.

For example, given: <code>["eat", "tea", "tan", "ate", "nat", "bat"]</code>
Return:
<pre>
[
["ate", "eat","tea"],
["nat","tan"],
["bat"]
]
</pre>

解题思路

这道题是将字符串进行分类，如果所含的字母相同即为同一类字符串。
换句话说，如果同一类的字符串中的字符进行排序后，他们就是同一个字符串。

我们可以定义一个map<string, int>，每一个排序后的串对应他的类别。对于一个新串，如果他属于其中某个类，则将其加入；如果不属于任何有一个类，则开一个新类来存储。

代码

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        vector<string> linner;
        map<string, int> mp;
        string copy;
        
        for (int i = 0; i < strs.size(); i++) {
            copy = strs[i];
            sort(copy.begin(), copy.end());
            if (mp.find(copy) == mp.end()) {
                //找不到所属的类别
                linner.clear();
                linner.push_back(strs[i]);
                mp[copy] = res.size();
                res.push_back(linner);
            } else {
                //存在所属的类别
                res[mp[copy]].push_back(strs[i]);
            }
        }
        
        return res;
    }
};