字母异位词分组 -526互联

记录一下从蒙蔽到理解的过程吧。

题目：给一个vector<string> 里面的字符串都是小写字母组成的，判断是vector<string>里是否存在完全一样的字母组成的字符串，有的话把他们分组。比如{"abc","cba"}就是一样的。

首先一开始想的是根据字符串字母的ASSIC码之和确定字符是否相等，但写完才发现不同字符串的值之和有可能相等，还要添加判定条件，最后还是回归到比较字母，太傻了。（不过似乎有大佬用质数代替字母，求他们的乘积来判断字符是否相等，可行但不多，因为是超长字符串的话，乘积过大，C++不允许这么长的整数，而且太大的话，可能会有哈希冲突）

好吧，那就暴力一点，利用哈希表，直接把每个字符串排序后的值作为key，key相同，就增加这个值对应的字符串作为value，所以哈希表类型是<string,vector<string>> 。时间复杂度O(nklogk) klogk是排序的时间。

代码如下

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string,vector<string>> hashtb;
vector<vector<string>> ans;
vector<string> strtp;
for(int i=0;i<strs.size();i++)
{
    string temp=strs[i];
    sort(temp.begin(),temp.end());

    if(hashtb.find(temp)!=hashtb.end())
    {
        auto it=hashtb.find(temp);
        it->second.push_back(strs[i]);
    }
    else 
    {
        strtp.push_back(strs[i]);
        hashtb.emplace(temp,strtp);
        strtp.clear();
    }
}

for(auto it:hashtb)
{
     ans.push_back(it.second);
}


return ans;

    }
};

还有有什么办法求解？

记录字符串每个字母出现的次数？反正就26个小写字母，设定一个数字字符串记录a~z的个数，判断字符串是否相等就好了。代码先不写了，就当回顾的时候练习用吧。