问题:
Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
分析:
1.可使用map作为容器。
2.将字符串按字母顺序进排序后作为map的key,将具有相同key的字符串的集合作为map的value。
3.统计value集合不小于1的添加到结果数据集中。
示例代码:
class Solution
{
public:
//将字符串按照字母顺序进排序,并返回排序后的新字符串(不改变原来字符串)
string sort(string str)
{
std::sort(str.begin(), str.end());
return str;
}
vector<string> anagrams(vector<string> &strs)
{
vector<string> result;//结果数据集
//如果给定的集合中字符串个数小于2则直接返回
if (strs.size() < 2)
{
return result;
}
//用于排序过程的map集合,key为按字母顺序排列的字符串,value为字符串在原来vector中的位置
map<string, vector<int>> anagramsMap;
string key;
string value;
int size = strs.size();
for (int i = 0; i < size; i++)
{
value = strs[i];
key = sort(value);
//如果map中不存在给定的key,则新添加一个pair
if (anagramsMap.find(key) == anagramsMap.end())
{
vector<int> anagrams(1, i);
anagramsMap.insert(std::make_pair(key, anagrams));
}
//否则,在key对应的value中添加字符串所在位置
else
{
anagramsMap[key].push_back(i);
}
}
//遍历map将value集合大于1的都放到result结果数据集中
for (map<string, vector<int>>::iterator iter = anagramsMap.begin(); iter != anagramsMap.end(); iter++)
{
vector<int> anagrams = iter->second;
int size = anagrams.size();
if (size > 1)
{
for (int i = 0; i < size; i++)
{
result.push_back(strs[anagrams[i]]);
}
}
}
return result;
}
};