Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[LeetCode] 49. Group Anagrams #49

Open
grandyang opened this issue May 30, 2019 · 0 comments
Open

[LeetCode] 49. Group Anagrams #49

grandyang opened this issue May 30, 2019 · 0 comments

Comments

@grandyang
Copy link
Owner

grandyang commented May 30, 2019


请点击下方图片观看讲解视频
Click below image to watch YouTube Video
Video

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 同步地址:

#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 打赏


---|---

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant