LeetCode：字母异位词分组

文章收录于LeetCode专栏
LeetCode地址

字母异位词分组

题目

  给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。所有输入均为小写字母，且不考虑答案输出的顺序。
  示例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] 仅包含小写字母

排序

算法思路

  异位词是由相同数量的字母根据不同顺序排序而组成的字符串，我们根据此特性可以知道只要分别对两个字符串进行排序，排序后形成的两个新字符串一定相等，所以我们可以通过对字符串进行排序后比较的方式来判断当前两个字符串是否是异位词。再识别出数组中有哪些异位词之后，可以使用一个额外的hash表将同一类异位词放hash表中，最后将其value组装返回。

编码

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

复杂度分析

  时间复杂度：使用Java自带的排序算法O(n log n)，同时最外层又对数组进行了遍历，因此时间复杂度为O(kn log n)；
  空间复杂度：使用了一个哈希表暂存数据，其空间复杂度为O(kn)。

哈希表辅助计数

算法思路

  因为所有词组都是有小写字母组成，所以我们可以用计数法对词组中出现的字母进行遍历计数，最后将结果放入到一个额外的hash表中，每次往hash表中放入数据时都需先看是否存在同样字符数量的词组，如果已经存在就往已有集合中追加，反之直接插入。这里需要特别说明一下，放入hash表中的key是每个词组中字母+总次数，如“tea”就会转换为“a1e1t1”存入hash表中。

编码

class Solution{
  public List<List<String>> groupAnagrams(String[] strs){
    Map<String, List<String>> map = new HashMap<>();
    for(String str: strs){
      int[] count = new int[26];
      for(int i=0; i<str.length(); i++){
        count[str.charAt(i) - 'a']++;
      }

      StringBuilder sb = new StringBuilder();
      for(int i=0; i<26; i++){
        if(count[i] != 0){
          sb.append('a' + i);
          sb.append(count[i]);
        }
      }
      List<String> list = map.getOrDefault(sb.toString(), new ArrayList<>());
      list.add(str);
      map.put(sb.toString(), list);
    }
    return new ArrayList(map.values());
  }
}

复杂度分析

   时间复杂度：因为对数组进行了一次遍历且在每次遍历中对词组中每个字母进行处理，所以时间复杂度为0(n(k+26))；
  空间复杂度：在使用哈希表暂存数据的基础之上，还额外使用了一个26长度的数组来存放每个字符的计数结果，最终的空间复杂度为O(n(k+26))。