题目描述

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

示例 1:

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

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

解释：

在 strs 中没有字符串可以通过重新排列来形成 "bat"。
字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。
字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此

题目分析

使用哈希表对字符串进行分组，重点是哈希算法的实现
– 字符串内从小到大排序：时间复杂度 O(n*k*log(k))
– 字符串26个字母分别计数：时间复杂度O(n*k)

n 是字符串个数，k是单个字符串长度

Java

public List<List<String>> groupAnagrams(String[] strs) {
    HashMap<String, List<String>> map = new HashMap<>();
    for (String str : strs) {
        String key = hash(str);
        if (map.get(key) == null) {
            map.put(key, new ArrayList<>());
        }
        List<String> list = map.get(key);
        list.add(str);
    }
    return map.values().stream().toList();
}

//    private String hash(String str) {
//        char[] array = str.toCharArray();
//        Arrays.sort(array);
//        return Arrays.toString(array);
//    }

private String hash(String str) {
    StringBuilder builder = new StringBuilder();
    int[] num = new int[26];
    for (int i = 0; i < str.length(); i++) {
        num[str.charAt(i) - 'a']++;
    }
    for (char ch = 'a'; ch <= 'z'; ch++) {
        int index = ch - 'a';
        if (num[index] > 0) {
            builder.append(ch);
            builder.append(num[index]);
        }
    }
    return builder.toString();
}

Kotlin

    fun groupAnagrams(strs: Array<String>): List<List<String>> {
        val map = HashMap<String, ArrayList<String>>()
        for (str in strs) {
            val key = hash(str)
            if (map[key] == null) {
                map[key] = ArrayList()
            }
            map[key]?.add(str)
        }
        return map.values.toList()
    }

//    fun hash(str: String): String {
//        val array = str.toCharArray()
//        Arrays.sort(array)
//        return Arrays.toString(array)
//    }

    fun hash(str: String): String {
        val builder = StringBuilder()
        val num = IntArray(26)
        for (ch in str) {
            num[ch - 'a']++
        }
        for (i in 0 until 26) {
            if (num[i] > 0) {
                builder.append('a' + i)
                builder.append(num[i])
            }
        }
        return builder.toString()
    }