算法-Hash/BitSet-字母异位词分组

1 题目概述

1.1 题目出处

https://leetcode-cn.com/problems/group-anagrams/

1.2 题目描述

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]

输出:

[

[“ate”,“eat”,“tea”],

[“nat”,“tan”],

[“bat”]

]

说明：

所有输入均为小写字母。

不考虑答案输出的顺序。

2 BitSet-针对单词内无重复字符

2.1 思路

利用BitSet，记录所有字母是否出现，出现则那一个bit为1

仅适用于输入字符串都为字母且单词内无重复字母的情况。对于单词内有重复字母的，暂时没有想到利用BitSet来解决的方式。

2.2 代码

class Solution {
       public List
   
    
     > groupAnagrams(String[] strs) {
           List
     
      
       > resultList = new ArrayList<>();        if(strs == null || strs.length == 0){
               return resultList;        }        if(strs.length == 1){
               List
       
         sList = new ArrayList<>();            sList.add(strs[0]);            resultList.add(sList);            return resultList;        }        Map
        
         
          > longMap = new HashMap<>(); List
          
            nullList = new ArrayList<>(); for(String str : strs){ if(str.length() == 0){ nullList.add(str); continue; } BitSet bitset = new BitSet(); char[] cs = str.toCharArray(); for(char c : cs){ bitset.set(c - 64); } long[] longs = bitset.toLongArray(); List
           
             sList = longMap.get(longs[0]); if(sList == null){ sList = new ArrayList
            
             (); longMap.put(longs[0], sList); resultList.add(sList); } sList.add(str); } if(nullList.size() > 0){ resultList.add(nullList); } return resultList; }}

2.3 时间复杂度

O(N*K)

其中N为字符串数组strs长度，K为最长字符串长度

2.4 空间复杂度

O(N*K)

其中N为字符串数组strs长度，K为最长字符串长度

3 整数分解为素数法则

3.1 思路

利用整数分解为素数法则，即每个整数都可以被分解为唯一组合的一堆素数的乘积。

所以每个单词，都可以拆分成单独字符后，将小写字符对应的Ascii码-'a'得到的数字下标对应的素数的乘积

但是该方法不适合单词过长，否则可能乘积溢出

3.2 代码

class Solution {
       public List
   
    
     > groupAnagrams(String[] strs) {
           List
     
      
       > resultList = new ArrayList<>();        if(strs == null || strs.length == 0){
               return resultList;        }        if(strs.length == 1){
               List
       
         sList = new ArrayList<>();            sList.add(strs[0]);            resultList.add(sList);            return resultList;        }        Map
        
         
          > longMap = new HashMap<>(); List
          
            nullList = new ArrayList<>(); int[] primes = { 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}; for(String str : strs){ if(str.length() == 0){ nullList.add(str); continue; } char[] cs = str.toCharArray(); long product = 1L; for(char c : cs){ product = product * primes[(c - 'a')]; } List
           
             sList = longMap.get(product); if(sList == null){ sList = new ArrayList
            
             (); longMap.put(product, sList); resultList.add(sList); } sList.add(str); } if(nullList.size() > 0){ resultList.add(nullList); } return resultList; }}