MENU

LeetCode49. Group Anagrams(模拟)

2019 年 02 月 17 日 • 阅读: 941 • LeetCode阅读设置

LeetCode49. Group Anagrams(模拟)

  • Medium
  • Accepted:290,927
  • Submissions:655,421

Given an array of strings, group anagrams together.

Example:

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:

  • All inputs will be in lowercase.
  • The order of your output does not matter.

链接

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

题意

给定一个字符串数组,对它们按anagrams进行分组,anagrams 的意思是由颠倒字母顺序而构成的字。比如abc/acb/bac/bca/cab/cba是同一个anagrams。保证所有的输入都是小写,输出顺序不唯一。

题解

  • 之前我们对anagram的处理是使用一个计数数组来进行判断,比如LeetCode438. Find All Anagrams in a String(滑动窗口
  • 回到这道题,我们可以先对所有的字符串进行排序,因为anagram排序后是同一个字符串,然后对排序后相同的字符串保存起来即可,时间复杂度$O(n*mlogm)$(m指字符串长度)
  • 因为全是小写字母,所以可以对字符串进行计数排序,然后再对相同字符串进行保存,时间复杂度$O(n*m)$

代码

  • Runtime: 56 ms, faster than 69.04% of C++ online submissions for Group Anagrams.
  • Memory Usage: 20.5 MB, less than 100.00% of C++ online submissions for Group Anagrams.
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map <string, vector<string>> umap;
        vector<vector<string>> ans;
        for (string s : strs)
        {
            string t = s;
            sort(t.begin(), t.end()); // 排序后相同的放到一起
            umap[t].push_back(s);
        }
        for (auto it : umap)
            ans.push_back(it.second);
        return ans;
    }
};
  • Runtime: 60 ms, faster than 48.78% of C++ online submissions for Group Anagrams.
  • Memory Usage: 20.3 MB, less than 100.00% of C++ online submissions for Group Anagrams.
class Solution {
public:

    string sortStr(string s) // 计数排序
    {
        int cnt[26] = {0};
        for (int i = 0; i < s.length(); ++i)
            cnt[s[i] - 'a']++;
        string t = "";
        for (int i = 0; i < 26; ++i)
            t += string(cnt[i], 'a' + i);
        return t;
    }

    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map <string, vector<string>> umap;
        vector<vector<string>> ans;
        for (string s : strs)
            umap[sortStr(s)].push_back(s);
        for (auto it : umap)
            ans.push_back(it.second);
        return ans;
    }
};

实际运行时间并没有变快反而还慢了4ms。有人说貌似对于数据范围比较小的时候,理论时间复杂度应该有一点“不稳定”。

参考


The end.
2019年2月17日 星期日