Boredom is for lazy people who have no imagination. 好吃懒做又脑袋空空的人才会觉得生活无聊。 问题描述 给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。 示例: 输入: ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ] 说明: 所有输入均为小写字母。 不考虑答案输出的顺序。 先排序再判断 今天这道题比较简单,字母异位词就是两个字符串中的字母都是一样的,只不过顺序被打乱了,这里要把他们找出来,然后放到一起。既然字母异位词的字母都是一样的,可以对字符串中的字符进行排序,生成一个新的字符串,如果生成新的字符串相同,那么他们就是字母异位词。代码比较简单,来看下 统计每个字母的个数 题目中说了所有输入均为小写字母,所以还可以只用一个数组,统计字符串中每个字符的个数,最终会生成一个新的字符串,如果生成新的字符串相同,说明他们是字母异位词,画个图看一下 1public List<List<String>> groupAnagrams(String[] strs) {
2 //边界条件判断
3 if (strs == null || strs.length == 0)
4 return new ArrayList<>();
5 //map中key存储的是字符串中字母排序后新的字符串
6 Map<String, List<String>> map = new HashMap<>();
7 for (int i = 0; i < strs.length; i++) {
8 //取出字符串,然后把它转化为字符数组
9 char[] c = strs[i].toCharArray();
10 //对字符数组进行排序
11 Arrays.sort(c);
12 //排序之后再把它转化为一个字符串
13 String keyStr = String.valueOf(c);
14 //判断map中有没有这个字符串,如果没有这个字符串,
15 //说明还没有出现和这个字符串一样的字母异位词,
16 //要新建一个list,把它存放到map中
17 if (!map.containsKey(keyStr))
18 map.put(keyStr, new ArrayList<>());
19 //把字符串存放到对应的list中
20 map.get(keyStr).add(strs[i]);
21 }
22 //最后返回
23 return new ArrayList<>(map.values());
24}
可以看到,只要是字母异位词,通过上面的方式转换,他们生成的字符串都是一样的
1public List<List<String>> groupAnagrams(String[] strs) {
2 //边界条件判断
3 if (strs == null || strs.length == 0)
4 return new ArrayList<>();
5 Map<String, List<String>> map = new HashMap<>();
6 for (String s : strs) {
7 char[] ca = new char[26];
8 //统计字符串中每个字符串出现的次数
9 for (char c : s.toCharArray())
10 ca[c - 'a']++;
11 //统计每个字符出现次数的数组转化为字符串
12 String keyStr = String.valueOf(ca);
13 if (!map.containsKey(keyStr))
14 map.put(keyStr, new ArrayList<>());
15 map.get(keyStr).add(s);
16 }
17 return new ArrayList<>(map.values());
18}
总结
由相同的字母组成的字符串才是字母异位词,既然有相同的字母,直接把他们排序是最容易想到的,所以第一种方式一般都能想到。第二种方式通过统计每个字符出现的次数,然后再把统计的结果转化为字符串也是可以实现的。
联系客服