49.字母异位词分组

难度：中等

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

提示：

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

解题思路

这里利用了 242 题的判断字母异位词的方法。

我的思路：

1. 设定结果列表，一个包含列表的列表 result，初始为空

2. 遍历 strs ，把 strs 中的每个字符串给提取出来，令其为 t

   1. 遍历结果列表 result 中的所有分组，获取每个字符串分组里的第一个字符串，令其为 s

   2. 调用 isAnagram(s , t) 方法来判断字符串是否为字母异位词

      • 若是字母异位词，则将 t 加入 s 所在的字符串分组
      • 若不是字母异位词，则换一个字符串分组进行比较

   3. 若遍历 result 结束仍未找到 t 所在的分组，则在 result 中新增分组，填入 t

3. 最后返回 result

我的代码

public List<List<String>> groupAnagrams(String[] strs) {
    List<List<String>> result = new ArrayList<>();
    for (int i = 0; i < strs.length; i++) {
        String t = strs[i];
        int j;
        for (j = 0; j < result.size(); j++) {
            List<String> strings = result.get(j);
            String s = strings.get(0);
            if (isAnagram(s, t)) {
                strings.add(t);
                break;
            }
        }
        if (j >= result.size()) {
            List<String> strings = new ArrayList<>();
            strings.add(t);
            result.add(strings);
        }
    }
    return result;
}

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return {
        false;
    }
    int[] record = new int[26];
    for (int i = 0; i < s.length(); i++) {
        record[s.charAt(i) - 'a']++;// 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
    }

    for (int i = 0; i < t.length(); i++) {
        if (record[t.charAt(i) - 'a'] > 0) {
            record[t.charAt(i) - 'a']--;
        } else {
            return false;
        }
    }
    return true;
}

时间复杂度：O(n^2 * k)，其中 n 是字符串数组的长度，k 是字符串的平均长度。

空间复杂度：O(n)

哈希表做法

字母相同，但排列不同的字符串，对其本身字符进行排序后一定会得到相同的字符串。

所以我们可以先创建一个哈希表 map，再遍历 strs，将遍历得到的每个字符串排序，比如“abcb”，“acbb”之类的字符串排序后都是“abbc”，在哈希表“abbc”这个 key 对应的 value 中就可以储存“abcb”，“acbb”这两个字符串。

代码展示

public List<List<String>> groupAnagrams(String[] strs) {
    HashMap<String, List<String>> map = new HashMap<>();
    for (int i = 0; i < strs.length; i++) {
        String s = strs[i];
        char[] chars = s.toCharArray();
        Arrays.sort(chars); // 对字符串中的字符排序
        String key = new String(chars); // 创建排序后的字符串作为键
        if (!map.containsKey(key)) {
            map.put(key, new ArrayList<>());
        }
        map.get(key).add(s); // 将原始字符串添加到对应的列表中
    }
    return new ArrayList<>(map.values());
}

时间复杂度：O(klogk)，其中 n 是字符串数组的长度，k 是字符串的平均长度。

空间复杂度：O(nk)

总结

数组就是简单的哈希表，但是数组的大小不是无限开辟的。