Leetcode 49.字母异位词分组

原题链接：Leetcode 49. Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
1
2

Example 2:

Input: strs = [""]
Output: [[""]]
1
2

Example 3:

Input: strs = ["a"]
Output: [["a"]]
1
2

Constraints:

• 1 <= strs.length <= 10⁴
• 0 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters.

---

方法一：排序

思路：

字母异位词值的顺序不同，但是进过排序后得到的字符串是相同的
那么就可以用排序后的字符串作为key，字母异位词链表作为value，维护一个哈希表
最后将哈希表中的内容取出来放到数组中返回即可

C++代码：

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        // <排序后的单词, 字母异位词链表>（有点像拉链法）
        unordered_map<string, vector<string>> mp;

        // 字母异位词排序之后是相同的
        for (auto str: strs) {
            string key = str;
            sort(key.begin(), key.end());
            mp[key].emplace_back(str);
        }

        vector<vector<string>> ans;
        // 每一个value都是一个包含同源异位词的数组
        for (auto it = mp.begin(); it != mp.end(); ++it) {
            ans.emplace_back(it->second);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

复杂度分析：

• 时间复杂度：O(nklogk)，遍历需要n，然后遍历每个单词的过程需要klogk的排序时间，k为单词最大长度
• 空间复杂度：O(nk)，n为单词数目，k为单词最大长度，哈希表不会超过nk这个范围