# Group Anagrams

## Question

### Problem Statement

Given an array of strings, group anagrams together.

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],
Return:

[
["ate", "eat","tea"],
["nat","tan"],
["bat"]
]


Note: All inputs will be in lower-case.

## 题解1 - 双重for循环(TLE)

Two Strings Are Anagrams 的升级版，容易想到的方法为使用双重for循环两两判断字符串数组是否互为变位字符串。但显然此法的时间复杂度较高。还需要 $O(n)$ 的数组来记录字符串是否被加入到最终结果中。

### Python

class Solution:
# @param strs: A list of strings
# @return: A list of strings
# @return: A list of strings
def anagrams(self, strs):

if len(strs) < 2 :
return strs
result=[]
visited=[False]*len(strs)
for index1,s1 in enumerate(strs):
hasAnagrams = False
for index2,s2 in enumerate(strs):
if index2 > index1 and not visited[index2] and self.isAnagrams(s1,s2):
result.append(s2)
visited[index2]=True
hasAnagrams = True
if not visited[index1] and hasAnagrams:
result.append(s1)
return result

def isAnagrams(self, str1, str2):
if  sorted (str1) == sorted(str2):
return True
return False


### C++

class Solution {
public:
/**
* @param strs: A list of strings
* @return: A list of strings
*/
vector<string> anagrams(vector<string> &strs) {
if (strs.size() < 2) {
return strs;
}

vector<string> result;
vector<bool> visited(strs.size(), false);
for (int s1 = 0; s1 != strs.size(); ++s1) {
bool has_anagrams = false;
for (int s2 = s1 + 1; s2 < strs.size(); ++s2) {
if ((!visited[s2]) && isAnagrams(strs[s1], strs[s2])) {
result.push_back(strs[s2]);
visited[s2] = true;
has_anagrams = true;
}
}
if ((!visited[s1]) && has_anagrams) result.push_back(strs[s1]);
}

return result;
}

private:
bool isAnagrams(string &s, string &t) {
if (s.size() != t.size()) {
return false;
}

const int AlphabetNum = 26;
int letterCount[AlphabetNum] = {0};
for (int i = 0; i != s.size(); ++i) {
++letterCount[s[i] - 'a'];
--letterCount[t[i] - 'a'];
}
for (int i = 0; i != t.size(); ++i) {
if (letterCount[t[i] - 'a'] < 0) {
return false;
}
}

return true;
}
};


### 源码分析

1. strs 长度小于等于1时直接返回。
2. 使用与 strs 等长的布尔数组表示其中的字符串是否被添加到最终的返回结果中。
3. 双重循环遍历字符串数组，注意去重即可。
4. 私有方法isAnagrams用于判断两个字符串是否互为变位词。

## 题解2 - 排序 + hashmap

leetcode 上此题的 signature 已经更新，需要将 anagrams 按组输出，稍微麻烦一点点。

### Python lintcode

class Solution:
# @param strs: A list of strings
# @return: A list of strings
# @return: A list of strings
def anagrams(self, strs):
strDict={}
result=[]
for string in strs:
if  "".join(sorted(string)) not in strDict.keys():
strDict["".join(sorted(string))] = 1
else:
strDict["".join(sorted(string))] += 1
for string in strs:
if strDict["".join(sorted(string))] >1:
result.append(string)
return result


### C++ - lintcode

class Solution {
public:
/**
* @param strs: A list of strings
* @return: A list of strings
*/
vector<string> anagrams(vector<string> &strs) {
unordered_map<string, int> hash;

for (int i = 0; i < strs.size(); i++) {
string str = strs[i];
sort(str.begin(), str.end());
++hash[str];
}

vector<string> result;
for (int i = 0; i < strs.size(); i++) {
string str = strs[i];
sort(str.begin(), str.end());
if (hash[str] > 1) {
result.push_back(strs[i]);
}
}

return result;
}
};


### Java - leetcode

public class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> result = new ArrayList<List<String>>();
if (strs == null) return result;

// one key to multiple value multiMap
Map<String, ArrayList<String>> multiMap = new HashMap<String, ArrayList<String>>();
for (String str : strs) {
char[] strChar = str.toCharArray();
Arrays.sort(strChar);
String strSorted = String.valueOf(strChar);
if (multiMap.containsKey(strSorted)) {
ArrayList<String> aList = multiMap.get(strSorted);
multiMap.put(strSorted, aList);
} else {
ArrayList<String> aList = new ArrayList<String>();
multiMap.put(strSorted, aList);
}
}

// add List group to result
Set<String> keySet = multiMap.keySet();
for (String key : keySet) {
ArrayList<String> aList = multiMap.get(key);
Collections.sort(aList);
}

return result;
}
}


### 源码分析

leetcode 中题目 signature 已经有所变化，这里使用一对多的 HashMap 较为合适，使用 ArrayList 作为 value. Java 中对 String 排序可先将其转换为 char[], 排序后再转换为新的 String.