49 字母异位词分组

一、题目

给你一个字符串数组，请你将 字母异位词（字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次）组合在一起。可以按任意顺序返回结果列表。

二、题解

思路： 互为字母异位词的字符串，按字母排序后会得到完全相同的字符串，因此可用「排序后的字符串」作为分组的键。遍历每个字符串，将其字符数组排序并转回字符串作为 key，把原字符串追加到哈希表中该 key 对应的列表里。最后返回哈希表所有 value（即各分组）的集合。

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // Map 的 Key 是排序后的字符串，Value 是原本的字符串列表
        Map<String, List<String>> map = new HashMap<>();

        for (String str : strs) {
            // 1. 将字符串转换为字符数组并排序
            char[] chars = str.toCharArray();
            Arrays.sort(chars);

            // 2. 将排序后的字符数组重新转回字符串，作为统一的 Key
            String key = new String(chars);

            // 3. 如果 Map 中还没有这个 Key，就先初始化一个空列表
            map.putIfAbsent(key, new ArrayList<>());

            // 4. 将原始字符串加入到对应的列表中
            map.get(key).add(str);
        }

        // 最后直接返回 Map 中所有的 Value 的集合
        return new ArrayList<>(map.values());
    }
}

时间复杂度：O(nklog⁡k)O(nk\log k)

空间复杂度：O(nk)O(nk)

评论