原題
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"].
解題
題意是在一組字符串中快鱼，找到所有出現(xiàn)兩次及以上的亂序字符串颠印。
思路是，實現(xiàn)一個映射抹竹，使得對于任意相同但亂序的字符串线罕，映射后的值相同。
這里的實現(xiàn)是窃判，將輸入的字符串轉(zhuǎn)為“字母+數(shù)字”的形式钞楼，其中數(shù)字為字母在字符串中出現(xiàn)的次數(shù)。例如“aabc”和“abca”的映射結(jié)果都是“a2b1c1”袄琳。
只需要遍歷一次數(shù)組询件，然后將所有的字符串都進行一次映射燃乍，并將映射值相同的字符串放在同一個數(shù)組內(nèi)。最后將所有大小超過1的數(shù)組組合起來即可宛琅。
代碼
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;
}
};
