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
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28

思路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;
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29

思路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;
  	    }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24

• 使用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()
  	        );
  	    }
  	```
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10