LeetCode49. Group Anagrams

1、题目链接

https://leetcode.com/problems/group-anagrams/

2、解题思路

这道题的意思是给你一个字符串数组，让你把含有相同字符的字符串（不考虑字符的顺序）进行分组，一开始我的想法是遍历整个数组，然后将每个字符串按照字典序排序，然后再把分组中的字符串按照字典序排序，最后比较两个字符串，如果相同就把他加到该组当中，如果不相同那就新建分组，毫无疑问这样做是能实现的，但是TLE（Time Limit Exceed）了，既然超时了，那就找找原因呗，排序可能会导致，两个for循环也可能会导致，刚开始除了两个for循环我还真没想到什么好的方法，然后我就考虑将排序给干掉，能不能不排序就知道两个字符串的字符想不相同呢？那肯定是有的了，按照以往的经验，碰到这种明目张胆提示了你只有小写字母（26个字符）的，那就肯定是要逼你用一个int数组来保存字符串中某个字符出现的次数，但是很不幸，又超时了，WTF，后来想到HashMap中的key是不能重复的，这不正好和我们的结果是一样的吗，key就是我们结果中的每一组的共同点（开头我们说过，字典序是一样的），所以，又要排序吗？NO，刚去掉的排序我不能自己打自己的脸>_<，最后还是借助我们的字符数组来完成这一操作了（其实我觉得这么做的结果也是排序，真香系列），是不是又多了一种字典序排列的方法。

3、代码

• Java

private static List<List<String>> groupAnagrams(String[] strs) {
    if (null == strs) return null;
    List<String> list;
    Map<String, List<String>> mapList = new HashMap<>();
    for (String s : strs) {
        int[] chArray = new int[26];
        for (int i = 0; i < s.length(); i++) {
            chArray[s.charAt(i) - 97]++;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < chArray.length; i++) {
            int chCount = chArray[i];
            while (chCount > 0) {
                sb.append((char) i + 97);
                chCount--;
            }
        }
        String key = sb.toString();
        if (mapList.containsKey(key)) {
            mapList.get(key).add(s);
        } else {
            list = new ArrayList<>();
            list.add(s);
            mapList.put(key, list);
        }
    }
    return new ArrayList<>(mapList.values());
}

• Python

def groupAnagrams(self,strs):
    resultMap = {}

    for str in strs:
        chArray = [0] * 26
        for ch in str:
            chArray[ord(ch) - 97] += 1
        key = ""
        for index in range(len(chArray)):
            count = chArray[index]
            while count > 0:
                key += chr(index + 97)
                count -= 1
        if resultMap.has_key(key):
            resultMap.get(key).append(str)
        else:
            resultMap[key] = [str]
    return resultMap.values()

• JavaScript

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    let resultMap = {};
    for (let j = 0; j < strs.length; j++) {
        let chArray = new Array(26);
        chArray.fill(0);
        for (let i = 0; i < strs[j].length; i++) {
            chArray[strs[j].charAt(i).charCodeAt() - 97]++;
        }
        let key = ""
        for (let i = 0; i < chArray.length; i++) {
            let count = chArray[i]
            while (count > 0) {
                key += String.fromCharCode(i + 97)
                count--
            }
        }
        if (resultMap.hasOwnProperty(key)) {
            resultMap[key].push(strs[j])
        } else {
            resultMap[key] = [strs[j]]
        }
    }
    let resultList = []
    for (let key in resultMap) {
        resultList.push(resultMap[key])
    }
    return resultList
};

4、提交结果