首页 > 代码库 > Leetcode--Anagrams

Leetcode--Anagrams

2024-07-15 07:04:42   223人阅读

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;
    }
};


联系
我们