【LeetCode】49. Group Anagrams解法及注释

谁借莪１个温暖的怀抱￠ 2022-07-26 04:14 159阅读 0赞

**49. Group Anagrams **

Total Accepted: 71543 Total Submissions: 262846 Difficulty: Medium  
Given an array of strings, group anagrams together.  
  
For example, given: \["eat", "tea", "tan", "ate", "nat", "bat"\],   
Return:  
  
\[  
  \["ate", "eat","tea"\],  
  \["nat","tan"\],  
  \["bat"\]  
\]  
Note:  
For the return value, each inner list's elements must follow the lexicographic order.

All inputs will be in lower-case.

【分析】

输入一个小写字母字符串数组，将所有“**变位词**”分别找出，并分组后返回。需要注意的是：返回的变位词组必须按字母序排序。关于如何一个字符串是否为给定字符串的“变位词”，同【LeetCode】242.Valid anagram. 本题中涉及的输入数据包含多个变位词组，因此需要分别判断，即通过循环遍历整个字符串数组。为了降低时间消耗，我们可以对输入字符串数组进行标记，如果某一字符串已经被确定为某一组变位词，则在后续寻找其它变位词组的时候，该字符串不再被遍历，这样时间复杂度为O(n)，但是，每一次判断字符串是否为变位词时，都需要遍历该字符串的所有位，这样的时间开销依然很大，为O(n2)，在LeetCode中运行时，会超时。

另一种更好的方法是，采用c++中的map容器，采用hash表的方法来解，基于这种方法，[网上有很多][Link 1]。

【解法及注释】

**方法一：普通方法**

class Solution {
    public:
        vector<vector<string>> groupAnagrams(vector<string>& strs) 
    	{
            
            vector<vector<string>> result;//定义存出结果的容器
            if(strs.empty())return result;//输入为空，直接返回
            
            vector<bool> used(strs.size(),false);//用于标记字符串是否已经被确定为变位词并分组存储
            
            int length=strs.size();
            sort(strs.begin(),strs.end());//对输入字符串按字母序进行排序，从而保证变位词分组自然有序
            
            for(int i=0;i<length;i++)
            {
                vector<string> temp;//存储变位词组
                if(!used[i])//如果输入字符串未被确定为变位词并分组，我们寻找其变位词
                {
                    used[i]=true;//标记已使用
                    temp.push_back(strs[i]);//存储
                    for(int j=i+1;j<length;j++)//循环遍历寻找其变位词
                    {
                        if(used[j])continue;//如果遍历过程中，遇到已经被使用过的字符串，则跳过
                        
                        bool flag=false;
                        flag=isAnagram(strs[j],strs[i]);//判断是否为变位词
                        if(flag)
                        {
                            temp.push_back(strs[j]);//如果是，则存储起来
    			used[j]=true;
                        }
                    }
                }
                result.push_back(temp);//循环结束，则这一组变位词全部找到，存储到结果容器
            }
            return result;
            
        }
        //用于判断两个字符串是否互为变位词，采用类似“哈希表”的策略
        bool isAnagram(string Strs, string Str)
        {
            int count[26]={0};
            for(int i=0;i<Str.size();i++)
            {
                count[Str[i]-'a']++;
            }
            for(int j=0;j<Strs.size();j++)
            {
                count[Strs[j]-'a']--;
            }
            for(int k=0;k<26;k++)
            {
                if(count[k]!=0)
                {
                    return false;
                }
            }
            return true;
        }
    };

**方法二：采用map，[链接][Link 2]**

class Solution {
    public:
        vector<vector<string>> groupAnagrams(vector<string>& strs) {
            unordered_map<string, vector<string>> hashMap;
            for(auto &v : strs) {
                string tmp(v);
                sort(tmp.begin(), tmp.end());
                hashMap[tmp].push_back(v);
            }
            vector<vector<string>> result(hashMap.size());
            int k = 0;
            for(auto it = hashMap.begin(); it != hashMap.end(); ++it, ++k) {
                result[k].swap(it->second);
                sort(result[k].begin(), result[k].end());
            }
            return result;
        }
    };

这个方法应该是最好的解法之一了：You are here!   Your runtime beats 98.68% of cppsubmissions.

[Link 1]: http://blog.csdn.net/guang09080908/article/details/47976481
[Link 2]: http://www.cnblogs.com/jdneo/p/5291304.html