Lintcode-乱序字符串

问题描述如下：
给出一个字符串数组S，找到其中所有的乱序字符串(Anagram)。如果一个字符串是乱序字符串，那么他存在一个字母集合相同，但顺序不同的字符串也在S中。

image.png

问题分析：
对于一个字符串，我们利用函数str2label(string str) 将其转化为“一个标签”。比如说“apple”变为“a1e1p2l1”这样的标签。对于乱序的字符串最终都会变为同一个标签。然后再利用map结构进行键值对的查找。

#include<vector>
#include<iostream>
#include<string>
#include<map>
using namespace std;
//给出一个字符串数组S，找到其中所有的乱序字符串(Anagram)。
//如果一个字符串是乱序字符串，那么他存在一个字母集合相同，
//但顺序不同的字符串也在S中。
class Solution {
public:    
    /**
     * @param strs: A list of strings
     * @return: A list of strings
     */
    string str2label(string str)
    {
          if(str=="") return str;//特殊情况考虑
        int hashtable[26]={0};
        for(int i=0;i<str.size();i++)
        {
            int index=str[i]-'a';
            hashtable[index]++;
        }
        string res;
        for(int i=0;i<26;i++)
        {
            if(hashtable[i]==0) continue;
            else
            {
                res.push_back(char('a'+i));
                res.push_back(char(hashtable[i])+'0');//如何将int变为char
            }
        }
        return res;
    }
    vector<string> anagrams(vector<string> &strs) {
        // write your code here
        map<string,vector<string>>m;//这里map键值对的设置很关键
        vector<string> result;
        for(int i=0;i<strs.size();i++)
        {
            string str=str2label(strs[i]);
            auto it=m.find(str);
            if(it==m.end()) {
                vector<string> res;
                res.push_back(strs[i]);
                m.insert(pair<string,vector<string> >(str,res));
            }
            else
            {
                it->second.push_back(strs[i]);
            }
        }
        for(auto it=m.begin();it!=m.end();it++)
        {
            if(it->second.size()>1){
                for(auto ite=it->second.begin();ite!=it->second.end();ite++)
                    result.push_back(*ite);
            }
        }
        return result;
    }
};