【Leetcode】49.字母异位分词

题目链接

49. 字母异位词分组

题目描述

解题思路

1.暴力法

两个for循环，分别判断两个字符串出现的字母个数是否相同，相同加入同一个List。时间复杂度基本等于O（n^2）,Leetcode上提交是超时的。

2.hash法

对暴力法进行改进，利用List记录字符串出现的字母个数相同的字符串，同时利用hash表记录List在ans二维列表的下标，这样只需要遍历一遍数组即可。

问题来了：hash表的值是下标，那hash表的键值该如何表示？

利用大小为26的数组，并初始化值为-1，统计每个字母出现的次数，如果两个字符串符合要求，那么两个字符串对应的数组一定是相同的，所以由数组值转换成的字符串也一定是相同的。所以hash表的键值为数组值转换成的字符串

3.利用质数实现hash法

解法思路与2相同，首先为26个字符赋值为26个质数，因为质数与质数的乘积是唯一的，这符合hash表键值的要求。所以hash表的键值为对应字母的质数乘积。

AC代码

1.暴力法

class Solution {
    public int[] cal(String temp,int[] count){
        for(int i = 0; i < temp.length(); i++){
            count[temp.charAt(i)-'a']++;
        }
        return count;
    }
    public boolean test(int[] countA,int[] countB){
        for(int i = 0; i < 26; i++){
            if(countA[i] != countB[i]) return false;
        }
        return true;
    }
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> ans = new LinkedList<>();
        boolean flags[] = new boolean[strs.length];
        for(int i = 0; i < strs.length; i++){
            if(flags[i] == true) continue;
            List<String> temp = new LinkedList<>();
            int countA[] = new int[26];
            countA = cal(strs[i],countA);
            temp.add(strs[i]);
            for(int j = i + 1; j < strs.length; j++){
                int countB[] = new int[26];
                countB = cal(strs[j],countB);
                if(test(countA,countB)){
                    temp.add(strs[j]);
                    flags[j] = true;
                }
            }
            ans.add(temp);
        }
        return ans;
    }
}

2.hash表法

class Solution {

    public String count(String temp,int[] tot){
        StringBuffer sb = new StringBuffer();
        for(int i = 0; i < temp.length(); i++){
            tot[temp.charAt(i)-'a']++;
        }
        for(int i = 0; i < tot.length; i++) sb.append(tot[i]);
        return sb.toString();
    }

    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> ans = new LinkedList<>();
        Map<String,Integer> hashTable = new HashMap<>();
        for(int i = 0; i < strs.length; i++){
            int[] countN = new int[26]; 
            Arrays.fill(countN,-1);
            String str = count(strs[i],countN);
            if(hashTable.containsKey(str)){
                int index = hashTable.get(str);
                ans.get(index).add(strs[i]);
            }else{
                List<String> temp = new LinkedList<>();
                temp.add(strs[i]);
                ans.add(temp);
                hashTable.put(str,ans.size()-1);               
            }
        }
        return ans;
    }
}

3.利用质数实现hash法

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map <double,vector<string> > m;
        double a[26]={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& s : strs)
        {
            double t = 1;
            for(char c : s)
                t *= a[c - 'a'];
            m[t].push_back(s);          //t为单词对应的质数乘积，m[t]则为该单词的异位词构成的vector
        }
        for(auto& n : m)                //n为键和值组成的pair
            res.push_back(n.second);
        return res;
    }
};