字母异位词分组

1. 原来的思路

遍历每个字符串，和 Map 中已有的 key 一个个比较：

新字符串
  ↓
遍历所有 key
  ↓
isAnagrams() 判断
  ↓
找到对应分组

isAnagrams() 每次需要遍历字符串：

O(L)

最坏情况下需要比较 n 个字符串：

O(n × L)

总共 n 个字符串：

O(n² × L)

2. 优化思路

不要一个个比较，而是给每个字符串生成一个 Anagram Key。

方法一：排序

把字符串排序：

eat → aet
tea → aet
ate → aet

tan → ant
nat → ant

相同的 Key 就属于同一组。

private String getAnagramKey(String str) {
    char[] chars = str.toCharArray();
    Arrays.sort(chars);
    return new String(chars);
}

时间复杂度：

排序一个字符串：O(L log L)
n 个字符串：O(n × L log L)

3. 方法二：统计字符次数

因为题目只有 a-z，可以直接统计每个字母出现次数：

private String getAnagramKey(String str) {
    int[] count = new int[26];

    for (char c : str.toCharArray()) {
        count[c - 'a']++;
    }

    return Arrays.toString(count);
}

例如：

eat
a = 1
e = 1
t = 1

tea
a = 1
e = 1
t = 1

得到相同的 Key，所以属于同一组。

时间复杂度：

一个字符串：O(L)
n 个字符串：O(n × L)

4. 三种方案对比

关键思想

不要遍历寻找“它属于哪个组”，而是给它生成一个 Key，让 HashMap 直接找到对应的组。

HashMap：

Key → List<String>

例如：

"aet" → ["eat", "tea", "ate"]
"ant" → ["tan", "nat"]
"abt" → ["bat"]