原题
Description
Given an array of strings, return all groups of strings that are anagrams.
Notice
All inputs will be in lower-case
Example
Given ["lint", "intl", "inlt", "code"], return ["lint", "inlt", "intl"].
Given ["ab", "ba", "cd", "dc", "e"], return ["ab", "ba", "cd", "dc"].
解题
题意是在一组字符串中，找到所有出现两次及以上的乱序字符串。
思路是，实现一个映射，使得对于任意相同但乱序的字符串，映射后的值相同。
这里的实现是，将输入的字符串转为“字母+数字”的形式，其中数字为字母在字符串中出现的次数。例如“aabc”和“abca”的映射结果都是“a2b1c1”。
只需要遍历一次数组，然后将所有的字符串都进行一次映射，并将映射值相同的字符串放在同一个数组内。最后将所有大小超过1的数组组合起来即可。
代码
class Solution {
public:
/*
* @param strs: A list of strings
* @return: A list of strings
*/
vector<string> anagrams(vector<string> &strs) {
// write your code here
map<string, vector<string>> m;
vector<string> res;
for (auto &str : strs) {
int alphabet[26] = { 0 };
for (auto c : str) {
alphabet[c - 'a']++;
}
string key;
key.reserve(10);
for (int i = 0; i < 26; i++) {
if (alphabet[i]) {
key += char(i + 'a');
key += alphabet[i];
}
}
auto it = m.find(key);
if (it == m.end()) {
m.insert({ key, vector<string>{str} });
} else {
it->second.push_back(str);
}
}
for (auto &p : m) {
if (p.second.size() > 1) {
res.insert(res.end(), p.second.begin(), p.second.end());
}
}
return res;
}
};
