第二题

49.字母异位词分组

6.png

7.png

解法一：遍历strs

对每个string进行排序，异位词的排序结构是一样的，在map中的key值也一样，在map中添加对应的vector，再将vector逐个添加到res中【常规方法】

#Python3
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        if not strs:
            return []
        res, dics = [],{}
        for s in strs:
            key = "".join(sorted(s))
            index = dics.setdefault(key,len(res))
            if index == len(res):
                res.append([s])
            else:
                res[index].append(s)
        return res

#C++
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map <string,vector<string> > m;
        for(string& s : strs)
        {
            string t = s;
            sort(t.begin(),t.end());
            m[t].push_back(s);   //t为单词的按顺序排列，作为key值，m[t]则为该单词的异位词构成的vector，作为value值
        }
        for(auto& n : m)                //n为键和值组成的pair
            res.push_back(n.second);
        return res;
    }
};

解法二：每个字符对应一个ASCII码，使用质数作为乘法因子 【参考题解，方法易理解】

#JAVA
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
                31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
                73, 79, 83, 89, 97, 101};


        // key 是字符串自定义规则下的哈希值
        Map<Integer, List<String>> hashMap = new HashMap<>();
        for (String s : strs) {
            int hashValue = 1;


            char[] charArray = s.toCharArray();
            for (char c : charArray) {
                hashValue *= primes[c - 'a'];
            }


            // 把单词添加到哈希值相同的分组
            if (hashMap.containsKey(hashValue)) {
                List<String> curList = hashMap.get(hashValue);
                curList.add(s);
            } else {
                List<String> newList = new ArrayList<>();
                newList.add(s);
                hashMap.put(hashValue, newList);
            }
        }
        return new ArrayList<>(hashMap.values());
    }
}

#C++
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map <double,vector<string> > m;
        double a[26]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101};
        for(string& s : strs)
        {
            double t = 1;
            for(char c : s)
            t *= a[c - 'a'];


            m[t].push_back(s);          //t为单词对应的质数乘积，m[t]则为该单词的异位词构成的vector
        }
        for(auto& n : m)                //n为键和值组成的pair
            res.push_back(n.second);
        return res;
    }
};

for(char c : s)//定义一个遍历字符c，让它分别等于字符串数组s里面的各个字符，然后执行下面的语句，当c被赋值为s里面所有字符各一次后，就会退出这个循环