博文中会简要介绍Leetcode P0049题目分析及解题思路。
“Group Anagrams”是一道比较基础的题目，主要考察对anagram的理解和对HashTable的灵活运用。
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.
对于anagram由于组成它们的字符完全相同，只是顺序不同，所有属于同一个anagram的字符串将拥有相同的排序后的字符顺序，所以可以将排序后的字符串当作键。
以下是Java的题解代码实现。
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> anagramGroup = new ArrayList<>();
if (strs == null || strs.length == 0)
return anagramGroup;
Map<String, List<String>> str2AnagramsMap = new HashMap<>();
for (String str: strs) {
char[] chars = str.toCharArray();
Arrays.sort(chars);
String key = String.valueOf(chars);
List<String> anagrams = str2AnagramsMap.getOrDefault(key, new ArrayList<>());
anagrams.add(str);
str2AnagramsMap.put(key, anagrams);
}
for (Map.Entry<String, List<String>> entry: str2AnagramsMap.entrySet())
anagramGroup.add(entry.getValue());
return anagramGroup;
}
}
以下是C++的题解代码实现。
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> anagram_group;
unordered_map<string, vector<string>> id2anagrams_map;
for (string str: strs) {
string str_id = str;
sort(str_id.begin(), str_id.end());
id2anagrams_map[str_id].push_back(str);
}
for (auto itr=id2anagrams_map.cbegin(); itr!=id2anagrams_map.cend(); ++itr) {
anagram_group.push_back(itr->second);
}
return anagram_group;
}
};