Anagrams

給一個數列，找出所有的 anagrams，思路非常簡單，因為如果彼此是 anagram的話，

彼此 sort 之後也是 anagram，所以只要開個 Hashmap 把 sort 後的字串當作 key，然後對應的 index當作 value

每次找到同樣的 key 時把 value 加上 index，最後只要數量超過一的 value就是 anagrams

public List<String> anagrams(String[] strs) {

    List<String> results = new ArrayList<>();
    if (strs.length == 0) {
        return results;
    }

    HashMap<String, ArrayList<Integer>> map = 
        new HashMap<String, ArrayList<Integer>>();
    for (int i = 0; i < strs.length; i++) {
        char[] chs = strs[i].toCharArray();
        Arrays.sort(chs);
        String sorted = String.valueOf(chs);
        if (map.containsKey(sorted)) {
            map.get(sorted).add(i);
        }
        else {
            ArrayList<Integer> values = new ArrayList<Integer>();
            values.add(i);
            map.put(sorted, values);
        }
    }
    for (ArrayList<Integer> values : map.values()) {
        if (values.size() > 1) {
            for (int i = 0; i < values.size(); i++) {
                results.add(strs[values.get(i)]);
            }
        }
    }
    return results;
}

time complexity 一開始我以為是 O( MN ), M 為平均字串長度，它會影響 Hash的查找，N是字串數量

但中間有個步驟是排序，排序會影響時間的，所以應該是 O(nk) (Hashmap 空間)* O(klogk)(排序時間)，k為最長字串長度