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.

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        
    }
}

分類(lèi)相同字母異序詞，給一個(gè)字符串?dāng)?shù)組，把相同字母異序詞放在一起。
Note:

• 所有的輸入都是小寫(xiě)
• 順序不重要

解：
思路一：暴力遍歷，一個(gè) List<Set<String>>，里面裝 set，set 裝 每個(gè)字符串的最小子串。依次遍歷，判斷當(dāng)前字符串的所有子串是否存在 set 中，存在，則加入到對(duì)應(yīng)位置；都不存在，則新建一個(gè) set。
思路二：在思路一的基礎(chǔ)上，改用map，把字符串轉(zhuǎn)成 char[] 排序，再轉(zhuǎn)成 String，這樣就不用 set 去判斷每個(gè)子串，直接判斷字符串是否存在即可。代碼如下：

public List<List<String>> groupAnagrams(String[] strs) {
    if (strs == null || strs.length == 0) {
        return new ArrayList<List<String>>();
    }
    Map<String, List<String>> map = new HashMap<String, List<String>>();
    for (String s : strs) {
        char[] ca = s.toCharArray();
        Arrays.sort(ca);
        String keyStr = String.valueOf(ca);
        if (!map.containsKey(keyStr)) {
            map.put(keyStr, new ArrayList<String>());
        }
        map.get(keyStr).add(s);
    }
    return new ArrayList<List<String>>(map.values());
}