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"]]

Example 2:

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

Example 3:

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

Constraints:

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

这道题让我们群组给定字符串集中所有的异位词,所谓的异位词就是两个字符串中字母出现的次数都一样,只是位置不同,比如 abc,bac, cba 等它们就互为异位词,那么如何判断两者是否是异位词呢,可以发现如果把异位词的字符顺序重新排列,那么会得到相同的结果,所以重新排序是判断是否互为异位词的方法,由于异位词重新排序后都会得到相同的字符串,以此作为 key,将所有异位词都保存到字符串数组中,建立 key 和当前的不同的异位词集合个数之间的映射,这里之所以没有建立 key 和其隶属的异位词集合之间的映射,是用了一个小 trick,从而避免了最后再将 HashMap 中的集合拷贝到结果 res 中。当检测到当前的单词不在 HashMap 中,此时知道这个单词将属于一个新的异位词集合,所以将其映射为当前的异位词集合的个数,然后在 res 中新增一个空集合,这样就可以通过其映射值,直接找到新的异位词集合的位置,从而将新的单词存入结果 res 中,参见代码如下:

解法一:

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map<string, int> m;
        for (string str : strs) {
            string t = str;
            sort(t.begin(), t.end());
            if (!m.count(t)) {
                m[t] = res.size();
                res.push_back({});
            }
            res[m[t]].push_back(str);
        }
        return res;
    }
};

下面这种解法没有用到排序,用一个大小为 26 的 int 数组来统计每个单词中字符出现的次数,然后将 int 数组转为一个唯一的字符串,跟字符串数组进行映射,这样就不用给字符串排序了,参见代码如下:

解法二:

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map<string, vector<string>> m;
        for (string str : strs) {
            vector<int> cnt(26);
            string t;
            for (char c : str) ++cnt[c - 'a'];
            for (int i = 0; i < 26; ++i) {
                if (cnt[i] == 0) continue;
                t += string(1, i + 'a') + to_string(cnt[i]);
            }
            m[t].push_back(str);
        }
        for (auto a : m) {
            res.push_back(a.second);
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/49

类似题目:

Valid Anagram

Group Shifted Strings

Find Resultant Array After Removing Anagrams

Count Anagrams

参考资料:

https://leetcode.com/problems/group-anagrams/

https://leetcode.com/problems/group-anagrams/discuss/19176/share-my-short-java-solution

https://leetcode.com/problems/group-anagrams/discuss/19200/10-lines-76ms-easy-c-solution-updated-function-signature

LeetCode All in One 题目讲解汇总(持续更新中…)

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,快快加入吧~)

知识星球 喜欢请点赞,疼爱请打赏❤️.

微信打赏

|

Venmo 打赏


—|—


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation