LeetCode 热题 100-49. 字母异位词分组

题目描述

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
示例 2:

输入: strs = [“”]
输出: [[“”]]
示例 3:

输入: strs = [“a”]
输出: [[“a”]]

提示：
1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

思路1

• 题目看起来比较简单，找出字符串数组中字母相同的字符串放在一个列表中，最后把所有列表返回
• 思路就是分两步，第一步找出来，第二步放在列表中

  • 首先是怎么找出字母相同的数组，简单思路就是把单词中的每个字母对应的ASCII值加起来，这样做的问题也很明显，会出现单词不一样，但是加起来的值一样，做了改进对字母的ASCII值做平方再相加，目的是为了两个字母的差值更大，减小单词不一样，值加起来一样的概率，但是这个不是正确解决思路，只是一种投机行为，这种方式只能减小但不能完全消除，所以按照这个思路的代码通过了107 / 120个测试用例

  • 第二步就是放在列表中，依照上述思路就想到了map，key是单词字母的ASCII值做平方再相加的结果，value就是一个列表里面是结果相同的单词，按照这种思路遍历完字符串数组再遍历map,将map的value添加到列表中返回，以下是代码

    public List<List<String>> groupAnagrams(String[] strs) {List<List<String>> res = new ArrayList<>();if (strs.length <= 0) {return res;}if (strs.length <= 1) {res.add(new ArrayList<>(Collections.singleton(strs[0])));return res;}Map<Integer, List<String>> listMap = new HashMap<>();for (String s : strs) {int sum = 0;for (int i = 0; i < s.length(); i++) {sum += s.charAt(i) * s.charAt(i);}Integer integer = Integer.valueOf(sum);List<String> list = listMap.get(integer);if (null == list) {list = new ArrayList<>();}list.add(s);listMap.put(integer, list);}for (Map.Entry<Integer, List<String>> value : listMap.entrySet()) {res.add(value.getValue());}return res;}
    

思路1优化

• 优化的思路就是怎么得到每个单词的那个唯一值，投机的方式就是再放大，平方不行就立方依次往上，果然4次方就通过了，但是这种思路只能减小不能完全解决，而且运算量也会增大。
• 在美版leetcode上看到大神的思路，用质数表示26个字母，把字符串的各个字母相乘，这样可保证字母异位词的乘积必定是相等的。这种原则上可以，但是一些过长的字符串乘积值会溢出。

  public static List<List<String>> groupAnagrams(String[] strs) {List<List<String>> res = new ArrayList<>();if (strs.length <= 0) {return res;}if (strs.length <= 1) {res.add(new ArrayList<>(Collections.singleton(strs[0])));return res;}int[] ints = new int[]{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101};Map<Long, List<String>> listMap = new HashMap<>();for (String s : strs) {long sum = 1;for (int i = 0; i < s.length(); i++) {sum *= ints[s.charAt(i) - 'a'];}Long integer = Long.valueOf(sum);List<String> list = listMap.get(integer);if (null == list) {list = new ArrayList<>();}list.add(s);listMap.put(integer, list);}for (Map.Entry<Long, List<String>> value : listMap.entrySet()) {res.add(value.getValue());}return res;
  }
  

思路2

• 先对每个字符串的从小到大排序，含有相同字母排完序的就一致了，以排完序的作为key，value放未排序的字符串列表

  public static List<List<String>> groupAnagrams(String[] strs) {List<List<String>> res = new ArrayList<>();if (strs.length <= 0) {return res;}if (strs.length <= 1) {res.add(new ArrayList<>(Collections.singleton(strs[0])));return res;}Map<String, List<String>> listMap = new HashMap<>();for (String s : strs) {String sort = s.chars().sorted().collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append).toString();List<String> list = listMap.get(sort);if (null == list) {list = new ArrayList<>();}list.add(s);listMap.put(sort, list);}for (Map.Entry<String, List<String>> value : listMap.entrySet()) {res.add(value.getValue());}return res;}
  

• 使用stream流操作

  	public static List<List<String>> groupAnagrams(String[] strs) {return new ArrayList<>(Arrays.stream(strs).collect(Collectors.groupingBy(s -> s.chars().sorted().collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append).toString())).values());}```