49-字母异位词分组

Leetcode题解
  1. 49、字母异位词分组
    1. 题目
    2. 题解

49、字母异位词分组

题目

aEvbe1.png

题解

方法1（未编写）：利用质数的性质，将26个字母转换为26个不同的质数，然后分别对每个字符串转换为字符串内每个字母转换的质数相乘的积，因此所有积相同的字符串就是异位词，最后将所有字符串进行hash存储即可，主键是乘积，值是字符串，最后得到的每个map中的字符串数组即是分组结果。

方法2（编写的答案）：将所有字符串按照字母升序排序，所有异位词必然会相同，然后同理对所有字符串进行Hash存储即可，主键为排序后的字符串，值为排序前字符串，最后得到的每个map中的字符串数组即是分组结果。

1、字母转质数，字符串转质数积，哈希即可；

2、字符串排序，异位词必相等，哈希即可；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        map<string, vector<string>> m;
        for (string& s : strs) {
            string tmp=s;
            sort(tmp.begin(), tmp.end());
            m[tmp].push_back(s);
        } 
        for (auto& r : m) {
            res.push_back(r.second);
        }
        return res;
    }
};

当前网速较慢或者你使用的浏览器不支持博客特定功能，请尝试刷新或换用Chrome、Firefox等现代浏览器