Letcode每日一题-字母异位词分组

太过爱你忘了你带给我的痛 2022-12-28 04:23 275阅读 0赞

题目描述如下:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYNTk5MQ_size_16_color_FFFFFF_t_70][]

是否位字母异位词的判定标准是是否具有相同的字符，如何判断两个字符串具有相同的字符，一种方法是循环

遍历，如果具有相同的字符则把对应的字符删除，依次循环，最后判断作为基准的字符串是否为空即可，这种比

较麻烦，而且 效率太低。

另外一种办法是对这些字符进行排序，则排序后的两个字符串相同，则为字母异位词。

在这里题目中说所有输入均为 小写字母，则还有一种方法就是用一个长度位26的数组存储各个字母出现的字数，

最后根据这个数组拼接字符串，如果拼接后的字符串的字符串相同则为字母异位词。

# 排序实现: #

public List<List<String>> groupAnagrams(String[] strs) {
            Map<String, List<String>> map = new HashMap<String, List<String>>();
            for (String str : strs) {
                char[] array = str.toCharArray();
                Arrays.sort(array);
                String key = new String(array);
                List<String> list = map.getOrDefault(key, new ArrayList<String>());
                list.add(str);
                map.put(key, list);
            }
            return new ArrayList<List<String>>(map.values());
        }

复杂度分析

时间复杂度：O(nklogk)，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度。需要遍历 n 个

字符串，对于每个字符串，需要 O(klogk) 的时间进行排序以及 O(1)的时间更新哈希表，因此总时间复杂度是

O(nklogk)。

空间复杂度：O(nk)，其中 n 是strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度。需要

用哈希表存储全部字符串。

# 利用26长度的数组实现： #

public List<List<String>> groupAnagrams(String[] strs) {
            HashMap<String,List<String>> result=new HashMap<>();
            for(int i=0;i<strs.length;i++){
                int[] charsCount=new int[26];
                for(int j=0;j<strs[i].length();j++){
                    charsCount[strs[i].charAt(j)-'a']++;
                }
                StringBuilder key=new StringBuilder();
                for(int j=0;j<charsCount.length;j++){
                    if(charsCount[j]==0){
                        continue;
                    }
                    char tmp=(char)(j+'a');
                    for(int z=0;z<charsCount[j];z++){
                        key.append(tmp);
                    }
                }
                if(result.get(key.toString())==null){
                    result.put(key.toString(),new ArrayList<>());
                }
                result.get(key.toString()).add(strs[i]);
            }
            ArrayList<List<String>> realResult=new ArrayList<>(result.size());
            for(List<String> value:result.values()){
                realResult.add(value);
            }
            return realResult;
        }

时间复杂度：O(n(k+∣Σ∣))，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度，Σ 是字

符集，在本题中字符集为所有小写字母，Σ∣=26。需要遍历 n 个字符串，对于每个字符串，需要 O(k) 的时

间计算每个字母出现的次数，O(∣Σ∣) 的时间生成哈希表的键，以及 O(1) 的时间更新哈希表，因此总时间

复杂度是 O(n(k+∣Σ∣))。

空间复杂度：O(n(k+∣Σ∣))，其中 nn 是 strs 中的字符串的数量，k是 strs 中的字符串的最大长度，Σ 是字

符集，在本题中字符集为所有小写字母，∣Σ∣=26。需要用哈希表存储全部字符串，而记录每个字符串中

每个字母出现次数的数组需要的空间为 O(∣Σ∣)，在渐进意义下小于 O(n(k+∣Σ∣))，可以忽略不计。

# 总结 #

就最后的运行表现来说排序的方法会更快一点

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYNTk5MQ_size_16_color_FFFFFF_t_70]: /images/20221120/848cc6d89c8c4f70b0e5419c0496ab6f.png