首页 > 代码库 > Leetcode--Anagrams

Leetcode--Anagrams

Problem Description:

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

分析:题目要求输出找出所有在字符串数组中的变形词,变形词的意思是指单词由相同的字母构成,只是字母在单词中的顺序不一样,比如:cat,tac,act,这三个单词即是变形词,思路是将所有的单词按照字母序的顺序排序后按照(key,value)的方式插入到multimap中,key表示排序后的单词,value表示原始单词,同时将唯一的key保存到一个set中,最后根据set中的key,查找multimap中的记录,如果记录数大于2,就输出所有的变形词。具体代码如下:

class Solution {
public:
    vector<string> anagrams(vector<string> &strs) 
    {
    vector<string> res;
	if(strs.empty())
		return res;
	multimap<string,string> strmap;	
	set<string> keys;
	for(int i=0;i<strs.size();i++)
	{
		string key=strs[i];
		sort(key.begin(),key.end());
		keys.insert(key);
		strmap.insert(make_pair(key,strs[i]));
	}
	for(set<string>::iterator i=keys.begin();i!=keys.end();i++)
	{
	    multimap<string,string>::size_type cnt=strmap.count(*i);
	    if(cnt>1)
	    {
	        multimap<string,string>::iterator iter=strmap.find(*i);
	        for(multimap<string,string>::size_type i=0;i!=cnt;i++)
	        {
		        res.push_back(iter++->second);
	        }
	    }
	}
	return res;
    }
};