首页 > 代码库 > leetcode第一刷_Anagrams

leetcode第一刷_Anagrams

今天再看这个题时,死活想不起这个单词是什么意思,查了字典都不知道,真晕了。

这个单词直译是颠倒顺序所形成的单词,实际上就是从集合中找出所有是由一组字母形成的那些单词,这种可以由很多组,即只要这组字母形成的字典中的单词多于1个,就要把这些单词输出出来。

怎么做呢?思路还是很简单的,要找出是由一组字母形成的单词,显然应该知道每一个单词是由哪些字母形成的,这当然可以建一个hash表,每次都比对hash表中的每一个位置的个数是不是相等,有没有更好的办法呢?有的,就是把这个hash表转化成一个string,这样看看string是不是相等的。那怎么转化呢?我用的方式是stringstream,这个流大家不是很熟悉,但是我发现它几乎是string与int之间转化最方便的工具了,可以把int喂给它,然后让他吐出string,好神奇。每个单词都可以计算这样一个string形式的hash表,把这个string作为map中的键,然后相同的那些单词可以放入对应的value,输出的时候,看一下后面value的size,大于1就输出出来,是不是很粗暴。

用这种方法一开始超时了,后来才发现是转化hash表的那里,修改了一下就好了,这种写法应该比较有适应性,注意每一个字母的个数之间最后插入一个特殊字符,防止连在一起产生错误。

string changeToString(int* t){
    ostringstream ss;
    for(int i=0;i<26;i++){
        ss<<t[i]<<"-";
    }
    return ss.str();
}

class Solution {
public:
    vector<string> anagrams(vector<string> &strs) {
        vector<string> res;
        int len = strs.size();
        if(len<=1)
            return res;
        map<string, vector<int> > smap;
        int t[30];
        for(int i=0;i<len;i++){
            memset(t, 0, sizeof(t));
            for(int j=0;j<strs[i].length();j++){
                t[strs[i][j]-‘a‘]++;
            }
            smap[changeToString(t)].push_back(i);
        }
        map<string, vector<int> >::const_iterator it = smap.begin();
        while(it != smap.end()){
            int tplen = (it->second).size();
            if(tplen>1){
                for(int i=0;i<tplen;i++)
                    res.push_back(strs[(it->second)[i]]);
            }
            it++;
        }
        return res;
    }
};