leetcode 49. Group Anagrams【素数相乘处理字符串哈希】

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

Given an array of strings, group anagrams together.

Example:

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:

• All inputs will be in lowercase.
• The order of your output does not matter.

rt

寻找的是交换位置后字符串一样的

关键在于如何哈希

查了半天

看了题解才想起来

将所有字符对应成一个素数

那么相乘之后的值就是可以唯一表示的

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        long long num[]={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,103,107,109,113};
        vector<long long>ans;
        vector<vector<string>> ana;
        for(int i=0;i<strs.size();i++){
            long long tot=1;
            for(int j=0;j<strs[i].length();j++)
                tot*=num[strs[i][j]-'a'];
            bool flag=1;
            for(int j=0;j<ans.size()&&flag;j++){
                if(ans[j]==tot)
                    flag=false,ana[j].push_back(strs[i]);
            }
           // printf("tot=%lld\n",tot);
            if(flag==1){
                ans.push_back(tot);
                vector<string>tmps;
                tmps.push_back(strs[i]);
                ana.push_back(tmps);
            }
                
        }
        return ana;
    }
};