[LeetCode] 49. Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:
Input: strs = [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”]
Output: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]

Example 2:
Input: strs = [“”]
Output: [[“”]]

Example 3:
Input: strs = [“a”]
Output: [[“a”]]

Constraints:
1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] consists of lowercase English letters.

字母异位词分组。

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/group-anagrams
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

暴力解思路

给定一个字符串数组，将字母异位词组合在一起。可以按任意顺序返回结果列表。字母异位词指字母相同，但排列不同的字符串。

做这个题之前，需要做如下几个题，对anagram的概念有所了解。

242. Valid Anagram
383. Ransom Note
387. First Unique Character in a String

此题比较粗暴的解法是把 input 里面所有的单词都按照字母排序，形成一个新的单词。比如”eat”排序后会成为”aet”，然后以”aet”为key，”eat”为 value 加入 hashmap。遍历完 input 之后，输出 hashmap 所有的 value 即可。

时间O(nlogn) - sort
空间O(n) - hashmap

Java实现

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<>();
        // corner case
        if (strs == null || strs.length == 0) {
            return res;
        }

        // normal case
        HashMap<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] letters = str.toCharArray();
            Arrays.sort(letters);
            String key = String.valueOf(letters);
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }
            map.get(key).add(str);
        }
        return new ArrayList<>(map.values());
    }
}

JavaScript实现

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
    const map = {};
    for (let str of strs) {
        const key = [...str].sort().join('');
        if (!map[key]) {
            map[key] = [];
        }
        map[key].push(str);
    }
    return Object.values(map);
};

最优解思路

但是如上不是最优解，最优解还是要通过counting sort的思路来做。对于每个单词，需要创建一个长度为26的数组（题目说了只有小写）来存这个单词里面每个字母都分别出现过几次。这样每个单词最后形成的数组会长类似这样

[ 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 ]
[ 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 ]
[ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 ]

然后把这个数组稍微变化一下，做成一个类似这样的string

10001000000000000001000000

把这样的 string 当做 hashmap 的 key。这样每个扫描过的单词都会变成这样，是异位词的单词们的 string 会长得一样，所以在 hashmap 中会被存到同一个 key 里面。最后以数组形式输出 hashmap 里面所有的 value 即可。

复杂度

时间O(mn) - n 个单词，单词平均长度是 m
空间O(n)

代码

Java实现

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            String letters = helper(str);
            if (!map.containsKey(letters)) {
                map.put(letters, new ArrayList<>());
            }
            map.get(letters).add(str);
        }
        return new ArrayList<>(map.values());
    }

    private String helper(String s) {
        char[] map = new char[26];
        for (char c : s.toCharArray()) {
            map[c - 'a']++;
        }
        String res = String.valueOf(map);
        // System.out.print(res);
        return res;
    }
}

JavaScript实现

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
    const map = new Map();
    for (const s of strs) {
        const letters = Array(26).fill(0);
        for (const c of s) {
            letters[c.charCodeAt(0) - 97]++;
        }
        console.log(letters);
        const key = letters.join("#");
        console.log(key);
        let val = [];
        if (map.has(key)) {
            val = map.get(key);
        }
        val.push(s);
        map.set(key, val);
    }

    return Array.from(map.values());
};