字母异位词分组

package main

import "strings"
import "sort"
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param strs string字符串一维数组 
 * @return string字符串二维数组
*/
func groupAnagrams( strs []string ) [][]string {
    cnt:=map[string][]string{}
    for _,s:=range strs{
        arr:=strings.Split(s,"")
        sort.Strings(arr)
        k:=strings.Join(arr,"")
        if _,ok:=cnt[k];!ok{
            cnt[k]=[]string{}
        }
        cnt[k]=append(cnt[k],s)
    }
    ans:=[][]string{}
    for _,v:=range cnt{
        ans=append(ans,v)
    }
    return ans
}

#include <unordered_map>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param strs string字符串vector 
     * @return string字符串vector<vector<>>
     */
    vector<vector<string> > groupAnagrams(vector<string>& strs) 
    {
        // write code here
        vector<vector<string>> result;
        unordered_map<string, vector<string>> map;
        for(auto& str:strs)
        {
            string key=str;
            sort(key.begin(), key.end());
            map[key].emplace_back(str);
        }
        for(auto it=map.begin();it!=map.end();it++)
        {
            result.emplace_back(it->second);
        }
        return result;
    }
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param strs string字符串vector 
     * @return string字符串vector<vector<>>
     */
    vector<vector<string> > groupAnagrams(vector<string>& strs) {
        // write code here
        vector<vector<string>> v;
        unordered_map<string, int> m;
        for(int i=0; i<strs.size(); i++){
            vector<string> v1;
            string s = strs[i];
            sort(s.begin(), s.end());
            if(m.find(s) != m.end()){
                for(int j=0; j<v.size(); j++){
                    if(v[j][0] == s){
                        v[j].push_back(strs[i]);
                    }
                }
            }else{
                m[s]++;
                v1.push_back(s);
                v1.push_back(strs[i]);
                v.push_back(v1);
            }
        }
        for(int i=0; i<v.size(); i++){
            v[i].erase(v[i].begin());
        }
        return v;
    }
};

class Solution {
public:
    /*
    方法一：排序
    由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，
    故可以将排序之后的字符串作为哈希表的键。
    
    复杂度分析
    时间复杂度：O(nklogk)，其中 n 是 }strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度。
               需要遍历 n 个字符串，对于每个字符串，需要 O(klogk) 的时间进行排序以及O(1) 的时间更新哈希表，
               因此总时间复杂度是 O(nklogk)。
    空间复杂度：O(nk)，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度。
               需要用哈希表存储全部字符串。
    */
    vector<vector<string>> groupAnagrams1(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;
        for (string& str: strs) {
            string key = str;
            sort(key.begin(), key.end());
            mp[key].emplace_back(str);
        }
        vector<vector<string>> ans;
        for (auto it = mp.begin(); it != mp.end(); ++it) {
            ans.emplace_back(it->second);
        }
        return ans;
    }
    
    /*
    方法二：计数

    1. 由于互为字母异位词的两个字符串包含的字母相同，因此两个字符串中的相同字母出现的次数一定是相同的，
       故可以将每个字母出现的次数使用字符串表示，作为哈希表的键。
    2. 由于字符串只包含小写字母，因此对于每个字符串，可以使用长度为 26 的数组记录每个字母出现的次数。
       需要注意的是，在使用数组作为哈希表的键时，不同语言的支持程度不同，因此不同语言的实现方式也不同。
       
    复杂度分析
    时间复杂度：O(n(k+∣Σ∣))，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度，Σ 是字符集，
               在本题中字符集为所有小写字母，∣Σ∣=26。需要遍历 n 个字符串，对于每个字符串，
               需要 O(k) 的时间计算每个字母出现的次数，O(∣Σ∣) 的时间生成哈希表的键，以及 O(1) 的时间更新哈希表，
               因此总时间复杂度是 O(n(k+∣Σ∣))。
    空间复杂度：O(n(k+∣Σ∣))，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的最大长度，Σ 是字符集，
               在本题中字符集为所有小写字母，∣Σ∣=26。需要用哈希表存储全部字符串，
               而记录每个字符串中每个字母出现次数的数组需要的空间为 O(∣Σ∣)，
               在渐进意义下小于 O(n(k+∣Σ∣))，可以忽略不计。
    */
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res ;
        map<string, vector<string>> map ;
        
        // 统计string的各字母频次,以频次为key直接加入队列
        for (auto s : strs) {
            string sts = string(26, '0') ;
            for (auto c : s)  ++ sts[c-'a'] ;
            map[sts].emplace_back (s) ;
        }
        for (auto e : map)  res.emplace_back(e.second) ;
        
        return res ;
    }
};