LeetCode Anagrams 題解：利用排序字符串作為鍵值分組異位詞

題目大意

給定字符串數組，返回所有由異位詞組成的分組。異位詞指字母相同但順序不同的單詞。輸入均為小寫。

解法：排序 + HashMap

對每個字符串排序得到標準化鍵值，相同鍵值的字符串互為異位詞。使用 HashMap> 收集。最後輸出大小 > 1 的所有列表。

Java 代碼

public List<String> anagrams(String[] strs) {
    List<String> res = new ArrayList<>();
    Map<String, List<String>> map = new HashMap<>();
    for (String str : strs) {
        char[] ch = str.toCharArray();
        Arrays.sort(ch);
        String key = new String(ch);
        if (map.containsKey(key)) map.get(key).add(str);
        else {
            List<String> list = new ArrayList<>();
            list.add(str);
            map.put(key, list);
        }
    }
    for (List<String> group : map.values())
        if (group.size() > 1) res.addAll(group);
    return res;
}

複雜度

設字符串平均長度 L，數組長度 N。排序 O(N L log L)，HashMap 操作 O(N)，總體高效。