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

曾经终败给现在 2023-03-13 05:10 3阅读 0赞

# 算法-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 思路 #

1.  利用BitSet，记录所有字母是否出现，出现则那一个bit为1
2.  仅适用于输入字符串都为字母且单词内无重复字母的情况。对于单词内有重复字母的，暂时没有想到利用BitSet来解决的方式。

## 2.2 代码 ##

class Solution { 
        public List<List<String>> groupAnagrams(String[] strs) { 
            List<List<String>> resultList = new ArrayList<>();
            if(strs == null || strs.length == 0){ 
                return resultList;
            }
            if(strs.length == 1){ 
                List<String> sList = new ArrayList<>();
                sList.add(strs[0]);
                resultList.add(sList);
                return resultList;
            }
            Map<Long,List<String>> longMap = new HashMap<>();
            List<String> 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<String> sList = longMap.get(longs[0]);
                if(sList == null){ 
                    sList = new ArrayList<String>();
                    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 思路 #

1.  利用整数分解为素数法则，即每个整数都可以被分解为唯一组合的一堆素数的乘积。
2.  所以每个单词，都可以拆分成单独字符后，将小写字符对应的`Ascii码-'a'`得到的数字下标对应的素数的乘积
3.  但是该方法不适合单词过长，否则可能乘积溢出

## 3.2 代码 ##

class Solution { 
        public List<List<String>> groupAnagrams(String[] strs) { 
            List<List<String>> resultList = new ArrayList<>();
            if(strs == null || strs.length == 0){ 
                return resultList;
            }
            if(strs.length == 1){ 
                List<String> sList = new ArrayList<>();
                sList.add(strs[0]);
                resultList.add(sList);
                return resultList;
            }
            Map<Long,List<String>> longMap = new HashMap<>();
            List<String> 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<String> sList = longMap.get(product);
                if(sList == null){ 
                    sList = new ArrayList<String>();
                    longMap.put(product, sList);
                    resultList.add(sList);
                }
                sList.add(str);
            }
            if(nullList.size() > 0){  
                resultList.add(nullList);
            }
            return resultList;
        }
    }

## 3.3 时间复杂度 ##

![在这里插入图片描述][20200511105956892.png]  
O(N\*K)

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

## 3.4 空间复杂度 ##

O(N\*K)

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

# 4 排序字符串 #

将每个单词先排序，然后跟HashMap中记录比对。

这种方法时间复杂度为`O(N*K*logK)`，空间复杂度依然是`O(N*K)`。

# 5 使用分隔符 #

将字符串中每个字符串统计，并使用分隔符做HashMap的Key。如：abbc，则转换后为`a1#b2#c1`。

[20200511105956892.png]: /images/20230312/e92b021f2edf499c9595239e82239b6a.png