面试题 10.02. 变位词组 - leetcode(C++)

本文主要是介绍面试题 10.02. 变位词组 - leetcode(C++)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、题目

面试题 10.02. 变位词组
这个题呀，非常有意思。为什么捏，和我实习面试阿里时遇到的题如出一辙哦！这不是巧了吗这不是！
下面来记录下自己的解题思路：

二、分析

1. 其实打眼一看，这个题可以用hash来解决，于是乎，二话不说我定义了一个 unordered_map<int,vector<string>>，这个hash的key代表是：字母编码成的整数，因为字母就26个，一个int可以表示32位，这样一个int就可以表达单词中的字母有无，有则该位为1，无则加勉（无则为0啊啊啊）；hash的value代表拥用相同字母的这些单词的数组。

["eat", "tea", "tan", "ate", "nat", "bat"]
对于eat而言，这三个字母处的位置为1，其余位置为0，按照以下的对应关系，来表示一个单词中每个字母的有无：
abcd efgh ijkl mnop qrst uvwx yz
0000 0000 0000 0000 0000 0000 00
则eat应该表示为：1000 1000 0000 0000 0001 0000 00，转化为int即可。

2. 但是这样有一个巨大的问题：如果单词中有重复字母那不是垮了吗那不是！比如：hello。
3. 于是，我想到了将int变为字符串这样就不用受限于其只可以表示1/0两种选择了。定义 unordered_map<string,vector<string>>，value同上，key同上，只不过换一种表达：

对于eat而言，这三个字母处的位置为1，其余位置为0，按照以下的对应关系，来表示一个单词中每个字母的：个数（不再是有无）：
abcd efgh ijkl mnop qrst uvwx yz
0000 0000 0000 0000 0000 0000 00（字符串）
则eat应该表示为：1000 1000 0000 0000 0001 0000 00（字符串）。
那如果重复了：比如hello就表示为：0000 1001 0002 0010 0000 0000 00（字符串）。

注意：不用担心一个单词中相同字母个数超过9了怎么办，后边可以用的字符多的是。就算一个单词中a有10个，表示出来也是：
:000 0000 0000 0000 0000 0000 00，且浅薄的英语常识告诉我，没那么多重复的。。。

最后遍历一遍hash表即可，这个hash的内存消耗挺大的，也可以再深入考虑一下压缩问题。

三、代码

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ans;
        unordered_map<string,vector<string>> result;
        for(int i = 0; i < strs.size(); i++){
            result[MyHash(strs[i])].push_back(strs[i]);
        }
        for(unordered_map<string,vector<string>>::iterator iter = result.begin(); iter != result.end(); iter ++){
            ans.push_back(iter->second);
        }
        return ans;
    }
    string MyHash(string s){
        string hashResult= "00000000000000000000000000"; // length = 26
        for(int i = 0; i < s.size(); i++){
            hashResult[s[i]-'a'] ++;
        }
        return hashResult;
    }
};

执行用时：20 ms , 在所有 C++ 提交中击败了99.58%的用户
内存消耗：18.6 MB, 在所有 C++ 提交中击败了33.06%的用户

这篇关于面试题 10.02. 变位词组 - leetcode(C++)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！