C/C++教程

面试题 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即可。
  1. 但是这样有一个巨大的问题:如果单词中有重复字母那不是垮了吗那不是!比如:hello。
  2. 于是,我想到了将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++)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!