LeetCode 49. Group Anagrams

Given an array of strings, group anagrams together.

Example:

Input: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
Output:
[
[“ate”,”eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]
Note:

All inputs will be in lowercase.
The order of your output does not matter.
解析：
该题目要求给定一组词语，按照同构词（错位词）分类，返回顺序无要求。
所谓的错位词就是两个字符串中字母出现的次数都一样，只是位置不同，比如abc，bac, cba等它们就互为错位词。
那么我们如何判断两者是否是错位词呢，我们发现如果把错位词的字符顺序重新排列，那么会得到相同的结果，所以重新排序是判断是否互为错位词的方法，由于错位词重新排序后都会得到相同的字符串，我们以此作为key，将所有错位词都保存到字符串数组中，建立key和字符串数组之间的映射，最后再存入结果res中即可。
[cc lang=”C++”]
class Solution {
public:
vector> groupAnagrams(vector& strs) {
vector> result;//最终结果
if (strs.empty())
return result;
int len = strs.size();
//将字符串数组按照字典顺序排序
sort(strs.begin(), strs.end());
//利用哈希思想构建map，将排序后相等的字符串存在相应的vector
map> mv;
for (int i = 0; i < len; i++) { string str = strs[i]; sort(str.begin(), str.end()); mv[str].push_back(strs[i]); } for (map >::iterator iter = mv.begin(); iter != mv.end(); iter++)
result.push_back(iter->second);
return result;
}
};
[/cc]
运行效果如下：

最开始计划采用深度优先的方式找到每个词语可能的各种排序，然后在进行判断当前生成的字符是否在字符串中，后来发现无法应对字符串存在重复的情况，所以只能采用哈希的这种方式。
参考：
https://blog.csdn.net/fly_yr/article/details/48163005
http://www.cnblogs.com/grandyang/p/4385822.html