題目描述（中等難度）
給定多個字符串传黄，然后把它們分類址遇。只要字符串所包含的字符完全一樣就算作一類，不考慮順序滋戳。
解法一
最通用的一種解法钻蔑，對于每個字符串啥刻，比較它們的每個字符出現(xiàn)的個數(shù)是否相等，相等的話就把它們放在一個 list 中去咪笑，作為一個類別可帽。最外層寫一個 for 循環(huán)然后一一比較就可以，還可以用一個等大的布爾型數(shù)組來記錄當前字符串是否已經(jīng)加入的了 list 窗怒。比較兩個字符串的字符出現(xiàn)的次數(shù)可以用一個 HashMap映跟，具體看代碼吧。
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> ans = new ArrayList<>();
boolean[] used = new boolean[strs.length];
for (int i = 0; i < strs.length; i++) {
List<String> temp = null;
if (!used[i]) {
temp = new ArrayList<String>();
temp.add(strs[i]);
//兩兩比較判斷字符串是否符合
for (int j = i + 1; j < strs.length; j++) {
if (equals(strs[i], strs[j])) {
used[j] = true;
temp.add(strs[j]);
}
}
}
if (temp != null) {
ans.add(temp);
}
}
return ans;
}
private boolean equals(String string1, String string2) {
Map<Character, Integer> hash = new HashMap<>();
//記錄第一個字符串每個字符出現(xiàn)的次數(shù)扬虚，進行累加
for (int i = 0; i < string1.length(); i++) {
if (hash.containsKey(string1.charAt(i))) {
hash.put(string1.charAt(i), hash.get(string1.charAt(i)) + 1);
} else {
hash.put(string1.charAt(i), 1);
}
}
//記錄第一個字符串每個字符出現(xiàn)的次數(shù)努隙，將之前的每次減 1
for (int i = 0; i < string2.length(); i++) {
if (hash.containsKey(string2.charAt(i))) {
hash.put(string2.charAt(i), hash.get(string2.charAt(i)) - 1);
} else {
return false;
}
}
//判斷每個字符的次數(shù)是不是 0 ，不是的話直接返回 false
Set<Character> set = hash.keySet();
for (char c : set) {
if (hash.get(c) != 0) {
return false;
}
}
return true;
}
時間復雜度：雖然看起來外層用了兩個 for 循環(huán)辜昵，但是我們通過 used 數(shù)組保證了每個字符串只會訪問 1 次荸镊，所以外層的復雜度是字符串數(shù)組的長度 O（n），判斷兩個字符串相等的函數(shù) equal 函數(shù)堪置，時間復雜度是字符串的最長長度 O（K）躬存。所以總共就是 O（nK）。
空間復雜度：O（NK）舀锨，用來存儲結(jié)果岭洲。
解法一算是比較通用的解法，不管字符串里邊是大寫字母坎匿，小寫字母盾剩，數(shù)字，都可以用這個算法解決碑诉。這道題的話彪腔，題目告訴我們字符串中只有小寫字母，針對這個限制进栽，我們可以再用一些針對性強的算法德挣。
下邊的算法本質(zhì)是，我們只要把一類的字符串用某一種方法唯一的映射到同一個位置就可以快毛。
解法二
參考官方給的解法格嗅。
我們將每個字符串按照字母順序排序，這樣的話就可以把 eat唠帝，tea屯掖，ate 都映射到 aet。其他的類似襟衰。
public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String, List<String>> hash = new HashMap<>();
for (int i = 0; i < strs.length; i++) {
char[] s_arr = strs[i].toCharArray();
//排序
Arrays.sort(s_arr);
//映射到 key
String key = String.valueOf(s_arr);
//添加到對應的類中
if (hash.containsKey(key)) {
hash.get(key).add(strs[i]);
} else {
List<String> temp = new ArrayList<String>();
temp.add(strs[i]);
hash.put(key, temp);
}
}
return new ArrayList<List<String>>(hash.values());
}
時間復雜度：排序的話算作 O（K log（K））,最外層的 for 循環(huán)贴铜，所以就是 O（n K log（K））。
空間復雜度：O（NK），用來存儲結(jié)果绍坝。
解法三
算術基本定理轩褐，又稱為正整數(shù)的唯一分解定理椎咧，即：每個大于1的自然數(shù)，要么本身就是質(zhì)數(shù)把介，要么可以寫為2個以上的質(zhì)數(shù)的積勤讽，而且這些質(zhì)因子按大小排列之后，寫法僅有一種方式拗踢。
利用這個脚牍，我們把每個字符串都映射到一個正數(shù)上。
用一個數(shù)組存儲質(zhì)數(shù) prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103}秒拔。
然后每個字符串的字符減去 ' a ' 莫矗，然后取到 prime 中對應的質(zhì)數(shù)飒硅。把它們累乘砂缩。
例如 abc ，就對應 'a' - 'a'三娩， 'b' - 'a'庵芭， 'c' - 'a'，即 0, 1, 2雀监，也就是對應素數(shù) 2 3 5双吆，然后相乘 2 * 3 * 5 = 30，就把 "abc" 映射到了 30会前。
public List<List<String>> groupAnagrams(String[] strs) {
HashMap<Integer, List<String>> hash = new HashMap<>();
//每個字母對應一個質(zhì)數(shù)
int[] prime = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103 };
for (int i = 0; i < strs.length; i++) {
int key = 1;
//累乘得到 key
for (int j = 0; j < strs[i].length(); j++) {
key *= prime[strs[i].charAt(j) - 'a'];
}
if (hash.containsKey(key)) {
hash.get(key).add(strs[i]);
} else {
List<String> temp = new ArrayList<String>();
temp.add(strs[i]);
hash.put(key, temp);
}
}
return new ArrayList<List<String>>(hash.values());
}
時間復雜度：O（n * K）好乐，K 是字符串的最長長度。
空間復雜度：O（NK）瓦宜，用來存儲結(jié)果蔚万。
這個解法時間復雜度，較解法二有提升临庇，但是有一定的局限性反璃，因為求 key 的時候用的是累乘，可能會造成溢出假夺，超出 int 所能表示的數(shù)字淮蜈。
解法四
參考這里，記錄字符串的每個字符出現(xiàn)的次數(shù)從而完成映射已卷。因為有 26 個字母梧田，不好解釋，我們假設只有 5 個字母，來看一下怎么完成映射裁眯。
首先初始化 key = "0#0#0#0#0#"肖方，數(shù)字分別代表 abcde 出現(xiàn)的次數(shù)，# 用來分割未状。
這樣的話俯画，"abb" 就映射到了 "1#2#0#0#0"。
"cdc" 就映射到了 "0#0#2#1#0"司草。
"dcc" 就映射到了 "0#0#2#1#0"艰垂。
public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String, List<String>> hash = new HashMap<>();
for (int i = 0; i < strs.length; i++) {
int[] num = new int[26];
//記錄每個字符的次數(shù)
for (int j = 0; j < strs[i].length(); j++) {
num[strs[i].charAt(j) - 'a']++;
}
//轉(zhuǎn)成 0#2#2# 類似的形式
String key = "";
for (int j = 0; j < num.length; j++) {
key = key + num[j] + '#';
}
if (hash.containsKey(key)) {
hash.get(key).add(strs[i]);
} else {
List<String> temp = new ArrayList<String>();
temp.add(strs[i]);
hash.put(key, temp);
}
}
return new ArrayList<List<String>>(hash.values());
}
時間復雜度： O（nK）。
空間復雜度：O（NK）埋虹，用來存儲結(jié)果猜憎。
總
利用 HashMap 去記錄字符的次數(shù)之前也有遇到過，很常用搔课。解法三中利用質(zhì)數(shù)相乘胰柑，是真的太強了。
更多詳細通俗題解詳見 leetcode.wang 爬泥。
