leetcode第49题

2022-09-26 109

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 时间复杂度：两层 for 循环，再加上比较字符串，如果字符串最长为 K，总的时间复杂度就是 O（n²K）。空间复杂度：O（NK），用来存储结果。解法一算是比较通用的解法，不管字符串里边是大写字母，小写字母，数字，都可以用这个算法解决。这道题的话，题目告诉我们字符串中只有小写字母，针对这个限制，我们可以再用一些针对性强的算法。下边的算法本质是，我们只要把一类的字符串用某一种方法唯一的映射到同一个位置就可以。

给定多个字符串，然后把它们分类。只要字符串所包含的字符完全一样就算作一类，不考虑顺序。

解法一

最通用的一种解法，对于每个字符串，比较它们的每个字符出现的个数是否相等，相等的话就把它们放在一个 list 中去，作为一个类别。最外层写一个 for 循环然后一一比较就可以，还可以用一个等大的布尔型数组来记录当前字符串是否已经加入的了 list 。比较两个字符串的字符出现的次数可以用一个 HashMap，具体看代码吧。

publicList<List<String>>groupAnagrams(String[] strs) {
List<List<String>>ans=newArrayList<>();
boolean[] used=newboolean[strs.length];
for (inti=0; i<strs.length; i++) {
List<String>temp=null;
if (!used[i]) {
temp=newArrayList<String>();
temp.add(strs[i]);
//两两比较判断字符串是否符合for (intj=i+1; j<strs.length; j++) {
if (equals(strs[i], strs[j])) {
used[j] =true;
temp.add(strs[j]);
                }
            }
        }
if (temp!=null) {
ans.add(temp);
        }
    }
returnans;
}
privatebooleanequals(Stringstring1, Stringstring2) {
Map<Character, Integer>hash=newHashMap<>();
//记录第一个字符串每个字符出现的次数，进行累加for (inti=0; i<string1.length(); i++) {
if (hash.containsKey(string1.charAt(i))) {
hash.put(string1.charAt(i), hash.get(string1.charAt(i)) +1);
        } else {
hash.put(string1.charAt(i), 1);
        }
    }
//记录第一个字符串每个字符出现的次数，将之前的每次减 1for (inti=0; i<string2.length(); i++) {
if (hash.containsKey(string2.charAt(i))) {
hash.put(string2.charAt(i), hash.get(string2.charAt(i)) -1);
        } else {
returnfalse;
        }
    }
//判断每个字符的次数是不是 0 ，不是的话直接返回 falseSet<Character>set=hash.keySet();
for (charc : set) {
if (hash.get(c) !=0) {
returnfalse;
        }
    }
returntrue;
}