49. Group Anagrams

发表于 | 分类于

每日一题 2019 - 03 - 31

题目：

Given an array of strings, group anagrams together.

Example:

1
2
3
4
5
6
7
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.

解法:

这个题让我们将来自相同字母组合的序列进行分类，思路如下：

  • 使用 map <string,int> 存放已经存在的字母序列，int 代表该字母组合存在多少个
  • 每次都将当前待查询的字母序列进行排序，保证所有相同字母组成的序列顺序相同
  • 如果不存在当前字母组合，创建新的 vector；否则，直接推入

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        int cnt=0,len=strs.size();
        vector<vector<string>>result(len);
        map<string,int>m;
        for(int i=0;i<strs.size();i++){
            string temp=strs[i];
            sort(temp.begin(),temp.end());
            if(m.find(temp)==m.end())
                m[temp]=cnt++;
            result[m[temp]].push_back(strs[i]);
        }
        result.resize(cnt);
        return result;
    }
};
0%
undefined