LeetCode49. Group Anagrams（模拟）

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。有人说貌似对于数据范围比较小的时候，理论时间复杂度应该有一点“不稳定”。

参考

• C++ unordered_map and counting sort

---

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