已知一組字符串，將所有anagram(由顛倒字母順序而構(gòu)成的字)放到一起輸出。
例如:["eat", "tea", "tan", "ate", "nat", "bat"]
返回:[ ["ate", "eat","tea"], ["nat","tan"], ["bat"] ]
LeetCode 49. Group Anagrams

思考

anagram分組: 若某兩個字符串，出現(xiàn)的各個字符數(shù)相同， 則它們應(yīng)該為同一分組。
例如:["eat", "tea", "tan", "ate", "nat", "bat"]
返回:[ ["ate", "eat","tea"], ["nat","tan"], ["bat"] ]

方法一：

哈 希 表 以 內(nèi) 部 進 行 排 序 的 各 個 單 詞 為 key ， 以 字 符 串 向 量 (vector<string>)為value，存儲各個字符數(shù)量相同的字符串(anagram)。

設(shè)置字符串到字符串向量的哈希表anagram，遍歷字符串向量strs中的 單詞strs[i]:
1)設(shè)置臨時變量str = strs[i]，對str進行排序。
2)若str未出現(xiàn)在anagram中，設(shè)置str到一個空字符串向量的映射。
3)將strs[i]添加至字符串向量anagram[str]中。 遍歷哈希表anagram，將全部key對應(yīng)的value push至最終結(jié)果中。

class Solution{
public:
      std::vector<std::vector<std::string>> groupAnagrams(std::vector<std::string> & strs){
          std::map<std::string, std::vector<std::string>> anagram;
//內(nèi)部進行排序的各個單詞為key，以字符串向量（vector<string>）為value，存儲各個字符數(shù)量相同的字符串（anagram）
          std::vector<std::vector<std::string>> result;//存儲最終的結(jié)果
          for(int i = 0; i < strs.size(); i++){
              std:: string str = strs[i];
              std::sort(str.begin(), str.end());//對str內(nèi)部進行排序
              if(anagram.find(str) == anagram.end){//無法在哈希表中找打str
                  std::vector<std::string> item;
                  anagram[str] = item;
               }
              anagram[str].push_back(strs[i]);
          }
          std::map<std::string, std::vector<std::string>>  :: iterator it;
          for(int = anagram.begin(); it != anagram.end(); i++){
              result.push_back((*it).second);
          }
          return result;
      }

};

方法二

哈希表以26個字母的字符數(shù)量(一個長度為26的vector，統(tǒng)計單詞中各個字 符的數(shù)量)為key，以字符串向量(vector<string>)為value，存儲各個字
符數(shù)量相同的字符串(anagram)。

算法設(shè)計
設(shè)置vector到字符串向量的哈希表anagram，遍歷字符串向量strs中的 單詞strs[i]:
1)統(tǒng)計strs[i]中的各個字符數(shù)量，存儲至vec。
2)若vec未出現(xiàn)在anagram中，設(shè)置vec到一個空字符串向量的映射。 3)將strs[i]添加至字符串向量anagram[vec]中。 遍歷哈希表anagram，將全部key對應(yīng)的value push至最終結(jié)果中。

  //將字符串str中的各個字符數(shù)量進行統(tǒng)計，存儲至vec
void change_to_vector(std::string & str, std::vector<int> & vec){
    for(int i = 0; i < 26; i++){
        vec.push_back(0);
    }
    for(int i= 0; i < str.length(); i++){
        vec[str[i] - 'a']++
    }
}
class Solution{
public:
    std::vector<std::vector<std::string>> groupAnagrams(std::vector<std::string> & strs){
        std::map<std::vector<int>, std::vector<std::string>> anagram;
        std::vector<std::vector<std::string>> result;
        for(int i =0; i < strs.size(); i++){
            std::vector<int> vec;
            change_to_vec(strs[i], vec);
            if(anagrams.find(vec)  == anagram.end()){
                std::vector<std::string> item;
                anagram[str[i]] = item;
            }
            anagram[vec].push_back(strs[i]);
        }
        std::map<std::vector<int>>,std::vector<std::string> :: iterator it;
        for(it = anagram.begin(); it != anagram.end(); it++){
              result.push_back((* it).second);
        }
        return result;
    }
};