leetcode面试经典150题——49 字母异位词分组

题目：字母异位词分组

描述：
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

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

leetcode链接

方法一：map
根据题目可知字母异位词 是由重新排列源单词的所有字母得到的一个新单词，即出现字母的数量是相同的，那么我们可以将这一特性作为关键字，将具有同一特性的字符串作为值进行存储，那么我们的定义应该为map<vector,vector>,遍历一遍数组，将具有相同特性的字符串加入到其值当中
时间复杂度：o(n) ,n为所有字符串的长度之和；
空间复杂度：o(n)，每个字符串均需要存储

vector<vector<string>> groupAnagrams(vector<string>& strs) {
   
        int n = strs.size();
        map<vector<int>,vector<string>>  map;
        for(int i=0;i<n;i++){
   
            vector<int> word(26,0);
            for(int j=0;j<strs[i].size();j++){
   //计算字母的出现次数
                word[strs[i][j]-'a']++;
            }
            map[word].push_back(strs[i]);//将字母异位词存储在一起
        }
        vector<vector<string> > ans;
        for(auto it=map.begin();it!=map.end();it++){
   //存储至答案中
            ans.push_back(it->second);
        }
        return ans;
    }

方法二：排序
对于字母异位词，我们将它进行排序，那么他们排序之后都是相同的
因此我们利用哈希表，将字母异位词排序后的字符串作为关键字，值为所有为该字符串的字母异位词
时间复杂度：o(n)
空间复杂度：o(n)

vector<vector<string>> groupAnagrams(vector<string>& strs) {
   
        int n = strs.size();
        unordered_map<string,vector<string>> map;
        for(string &s:strs){
   
            string tag = s;
            sort(tag.begin(),tag.end());//排序
            map[tag].push_back(s);//存储字母异位词
        }
        vector<vector<string>> ans;
        for(auto it=map.begin();it!=map.end();it++){
   
            ans.push_back(it->second);
        }
        return ans;
    }