题目链接
题目描述
Given an array of strings, group anagrams together.
*Example: *
1 | Input: ["eat", "tea", "tan", "ate", "nat", "bat"], |
*notes: *
- All inputs will be in lowercase.
- The order of your output does not matter.
解题思路(by myself)
问题: 如何比较两个 string 是由同一个字符串颠倒顺序组成的?
将两个字符串 s1, s2 按照字典序排列,如果s1 和 s2 的字典序排列结果相同,则满足 anagrams
在C++ 中,将 string s 按照字典序排列的代码为:
sort(s.begin(), s.end())
我的思路为:
变量:
ans: 返回结果
compare: 存储不同 string 的字典序排列(相同的字典序排列只存储一次)
line: 字典序排列在 ans 中对应的行数
过程:
- 遍历字符串数组 strs 的每一个字符串 s:
- 计算 s 的字典序排列,存储在 word 中
- 如果 word 在 compare 中存在,获取 line 中对应的行数,插入
- 如果 word 在 compare 中不存在,compare 和 line 中插入 word 和新的行数,ans 另起一行插入 s
- 遍历字符串数组 strs 的每一个字符串 s:
但是,按照该思路的话,会有 time limited 报错。
我的解法如下:
1 | vector<vector<string> > groupAnagrams(vector<string>& strs) { |
解题思路(by others)
利用 unordered_map 来存储,key 值为字典序,value 值为满足该字典序的 string 数组。因为 unordered_map 利用哈希表实现,因此查找效率提高,解决 time limited 的报错。
解法如下:
1 | vector<vector<string> > groupAnagrams(vector<string>& strs) { |
在这里,复习一下 unordered_map。
声明:
1
unordered_map<string, vector<string> > word_map;
其中,
string
为 key 值的类型,vector<string>
为 value 值的类型。插入元素:
1
word_map[word].push_back(strs[i]);
因为
word_map[word]
的对应类型为vector<string>
,因此直接用push_back
插入元素。遍历:
1
2
3
4for (auto it = word_map.begin(); it != word_map.end(); it++) {
key = it->first;
value = it->second;
}first
和second
分别为 key 值和 value 值