【leetcode】字母异位词分组

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

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"], 输出: [   ["ate","eat","tea"],   ["nat","tan"],   ["bat"] ]

说明：

    所有输入均为小写字母。     不考虑答案输出的顺序。

分析：两个方法

1.对每个单词进行字典序排序，排序结果相同的自然是同一分组

时间复杂度：O(N*K*log K),K为最长单词长度

空间复杂度：O(N*K)

2.对每个单词按计数分类

可以采用map，也可以采用数组，建议利用素数的性质来使用数组进行计数

每个小写字符对应一个素数，素数相乘的结果和素数乘的先后顺序无关，所以对每个单词可以生成一个特征码，只要单词中的字符的数量和种类相同，那么生成的特征码也是一样的

时间复杂度：O(N*K)

空间复杂度：O(N)

class Solution { public: vector<vector<string> > groupAnagrams(vector<string>& str) { int mod=1000000007; vector<vector<string> > vv; map<long long,vector<string> > mm; map<long long ,vector<string> >::iterator it; int n=str.size(); if(n==0) return vv; for(int i=0;i<n;i++) { long long ans=1; int m=str[i].size(); for(int j=0;j<m;j++) { } mm[ans].push_back(str[i]); } for(it=mm.begin();it!=mm.end();it++) { vv.push_back(it->second); } return vv; } };