【哈希】字母异位词

有效的字母异位词

242. 有效的字母异位词

给了两个单词 s 和 t，要判断它们是不是字母异位词。

所谓字母异位词是指由相同种类和数目的字母组合而成的单词，例如这一对组合："anagram" 与 "nagaram"。

一个直观的思路是对字符串内部字符按照字典序排序。若两字符串排序结果相同，则说明它们是异位词。

然而，对字符串内部的字符进行排序，通常需要 $O(n\log n)$ 的时间复杂度。其实还有更好的 $O(n)$ 解法——统计单词的字符频率。

我们使用计数器 counter 来统计 s 的字符频率。

遍历 t 时，我们对 counter 进行相反的操作，即将对应字符的计数减一。

最终，若计数器中的所有计数都归零，则 s 和 t 就是一组字母异位词。

基于这一思路，不难写出代码：

▼
java
复制代码
public boolean isAnagram(String s, String t) {
 if (s.length() != t.length()) {
     return false;
 }
 // 由于题目保证单词仅由小写字母构成，因此用数组来模拟 Map<Character, Integer>。
 int[] counter = new int[26];
 for (int i = 0; i < s.length(); i++) {
     counter[s.charAt(i) - 'a']++;
 }
 for (int i = 0; i < t.length(); i++) {
     counter[t.charAt(i) - 'a']--;
 }
 for (int count : counter) {
     if (count != 0) {
         return false;
     }
 }
 return true;
}

字母异位词分组

49. 字母异位词分组

题目给我们一个仅有小写字母构成的单词数组 strs，并要求我们将字母异位词组合在一起。

显然，我们要将这些单词按照是否为同一类字母异位词这一标准进行分组。那么这个标准要如何表示呢？

一个较为直接的想法是对每个单词内部的字符按照字典序排序。若两个单词属于同一类字母异位词，则它们排序后的结果一定相同。因此，我们可以将排序后的字符串作为 key，将对应的单词列表作为 value。

除此之外，还有时间复杂度更优的方案，即继续利用字符频率。

这里有一个难点，我们怎么用字符频率构建标准呢？

我的想法是利用 counter 构造一个压缩后的字符串表示：按照字典序依次记录每个出现过的字符及其频率。例如，"nagaram" 可以被压缩表示为 "a3g1n1r1"。

属于同一类字母异位词的单词，其字符频率完全相同，因此一定可以得到相同的字符串表示。这样，我们就可以将这个字符串作为 key。

基于这一思路，不难写出如下代码：

▼
java
复制代码
public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> group = new HashMap<>();
    for (String str : strs) {
        String key = buildFrequencyKey(str);
        group.computeIfAbsent(key, s -> new ArrayList<>())
                .add(str);
    }
    return new ArrayList<>(group.values());
}

private String buildFrequencyKey(String str) {
    if (str.isEmpty()) {
        return str;
    }
    StringBuilder res = new StringBuilder();
    int[] counter = new int[26];
    for (int i = 0; i < str.length(); i++) {
        counter[str.charAt(i) - 'a']++;
    }
    for (int i = 0; i < counter.length; i++) {
        if (counter[i] > 0) {
            res.append((char)(i + 'a'));
            res.append(counter[i]);
        }
    }
    return res.toString();
}