leetcode 49 字母异位词分组(哈希映射map)-白红宇

leetcode 49 字母异位词分组(哈希映射map)

阅读量：2434 次

发布时间：2019-05-10

本文共 2152 字，大约阅读时间需要 7 分钟。

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],

输出:

[

[“ate”,“eat”,“tea”],

[“nat”,“tan”],

[“bat”]

]

说明：

所有输入均为小写字母。

不考虑答案输出的顺序。

已知一组字符串，将所有由颠倒字母顺序而构成的字放到一起输出

某两个字符串字符字母相同就应该分为一组

思考：

如何建立哈希表，怎样设计哈希表的key与value,就可将各个字符数相同的字符映射到一起

哈希表以内部进行排序的各个单词为key，以字符串向量(vector< string>)为value，储存各个字符数量相同的字符串

算法思路1：

设置字符串到字符向量的哈希表anagram，遍历字符串向量strs中的单词strs[i]：

1）设置临时变量str = str[i]，对str进行排序

2）若str未出现在anagram中，设置str到一个空字符串向量的映射

3）将strs[i]添加至字符串向量anagram[str]中

遍历哈希表anagram，将全部Key对应的value push至最终结果

class Solution {
   public:    vector
   
    
     > groupAnagrams(vector
     
      & strs) {
           map
      
       > anagram;        vector
       
        
         > result; for (int i = 0; i < strs.size(); i++){ string str = strs[i]; sort(str.begin(), str.end()); if (anagram.find(str) == anagram.end()){ vector
         
           item; anagram[str] = item; //以排序后的strs[i]作为key } anagram[str].push_back(strs[i]); //在对应的字符串向量中push结果 } map
          
           >::iterator it; for (it = anagram.begin(); it != anagram.end(); it++){ result.push_back((*it).second); } return result; }};

哈希表以26个字母的字符数量(一个长度为26的vector，统计单词中各个字符的数量)为key，以向量字符串(vector< string>)为value，存储各个字符数量相同的字符串(anagram)

算法思路2：

设置字符串到字符向量的哈希表anagram，遍历字符串向量strs中的单词strs[i]：

1）统计strs[i]中的各个字符数量，存储至vec

2）若vec未出现在anagram中，设置一个vec到一个空字符串向量的映射

3）将strs[i]添加至字符串向量anagram[vec]中

遍历哈希表anagram，将全部Key对应的value push至最终结果

class Solution {
   public:    vector
   
    
     > groupAnagrams(vector
     
      & strs) {
           map
      
       
        , vector
        
         > anagram; vector
         
          
           > result; for (int i = 0; i < strs.size(); i++){ vector
           
             vec; change_to_vector(strs[i], vec); if (anagram.find(vec) == anagram.end()){ vector
            
              item; anagram[vec] = item; //以排序后的strs[i]作为key } anagram[vec].push_back(strs[i]); //在对应的字符串向量中push结果 } map
             
              
               , vector
               
                >::iterator it; for (it = anagram.begin(); it != anagram.end(); it++){ result.push_back((*it).second); } return result; }private: //将字符串str中的各个字符数量进行统计，存储至vec void change_to_vector(string &str, vector
                
                  &vec){ for (int i = 0; i < 26; i++){ vec.push_back(0); } for (int i = 0; i < str.length(); i++){ vec[str[i] - 'a']++; } }};