LeetCode——字母异位词分组

NO.49 字母异位词分组中等

思路一：算术基本定理法 这是一个非常巧妙的方法。

算术基本定理(唯一分解定理)：任何一个大于 1 的自然数都可以分解成一些素数的乘积；并且在不计次序的情况下，这种分解方式是唯一的。 ——欧几里得

先申请一个包含26个不重复素数的数组prime[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103 ]，一个HashMap<Interger,List<String>>。
将字符串的每个字符减去’a’映射出对应的素数，将字符串和其映射出的素数的乘积作为键值对保存到哈希表中，最后哈希表中的所有List<String>作为结果集即可。

public List<List<String>> groupAnagrams(String[] strs) {
    if (strs==null||strs.length==0)return new ArrayList<>();
    //26个字母分别对应一个素数
    int[] prime=new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103};
    HashMap<Integer,List<String>> map=new HashMap<>();
    for (int i=0;i<strs.length;i++){
        int key=1;
        for (int j=0;j<strs[i].length();j++){
            //字符串的每个字符对应的素数的乘积key
            key*=prime[strs[i].charAt(j)-'a'];
        }
        if (map.containsKey(key)){
            map.get(key).add(strs[i]);
        }else {
            map.put(key,new ArrayList<String>());
            map.get(key).add(strs[i]);
        }
    }
    return new ArrayList<>(map.values());
}

ps：此方法有一个严重的问题，key很容易发生溢出。最直接的解决方法就是采用大数类型的key。

时间复杂度：O(n*k)，k是字符串的最大长度

思路二：排序数组分类法 申请一个HashMap<String,List>，将每个字符串中的字符按照字典顺序排序后作为key、字符串本身作为value中的集合的元素。

public List<List<String>> groupAnagrams(String[] strs) {
    if (strs==null||strs.length==0)return new ArrayList<>();
    HashMap<String,List<String>> map=new HashMap<>();
    //遍历每个字符串
    for (int i=0;i<strs.length;i++){
        //将么个字符串中的字符按字典排序后作为key
        char[] chars = strs[i].toCharArray();
        Arrays.sort(chars);
        String key = String.valueOf(chars);
        //key作为key，strs[i]作为value集合中的元素
        if (!map.containsKey(key))map.put(key,new ArrayList<>());
        map.get(key).add(strs[i]);
    }
    return new ArrayList<>(map.values());
}

时间复杂度：O(n*klogk) n为元素个数，k为最长字符串长度，klogk是排序的时间复杂度

思路三：字符计数分类法 和思路三差不多的想法，申请一个HashMap<String,List>，将每个字符串中字符出现的字数统计之后转换成”n#n#n#n#….”形式的字符串作为key。例如abc转换为”1#1#1#0#0#…”。

public List<List<String>> groupAnagrams(String[] strs) {
    if (strs==null||strs.length==0)return new ArrayList<>();
    HashMap<String,List<String>> map=new HashMap<>();
    for (int i=0;i<strs.length;i++){
        //统计字符串中每个字符出现的次数
        int[] count=new int[26];
        for (int j=0;j<strs[i].length();j++){
            count[strs[i].charAt(j)-'a']++;
        }
        //将计数器转换成n#n#n#n#格式
        String key="";
        for (int k=0;k<count.length;k++){
            key+=count[k]+"#";
        }
        if (!map.containsKey(key))map.put(key,new ArrayList<>());
        map.get(key).add(strs[i]);
    }
    return new ArrayList<>(map.values());
}

时间复杂度：O(nk)，k是最长字符串的长度

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github

NO.49 字母异位词分组 中等

NO.49 字母异位词分组中等