首页 > 代码库 > Anagrams
Anagrams
Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
参考:http://www.cnblogs.com/AnnieKim/archive/2013/04/25/3041982.html
首先简单介绍一下Anagram(回文构词法)。Anagrams是指由颠倒字母顺序组成的单词,比如“dormitory”颠倒字母顺序会变成“dirty room”,“tea”会变成“eat”。
回文构词法有一个特点:单词里的字母的种类和数目没有改变,只是改变了字母的排列顺序。
由此我们可以想到,只要将几个单词按照字母顺序进行排序,就可以通过比较判断他们是否是anagrams。
思路:用map<string, int>记录排序后的字符串以及首次出现的位置。
1. 从strs的第一个元素开始遍历,首先对元素进行排序得到s;
2. 在map里查找s;
3. 若不存在,将s以及该元素的下标存入map<string ,int>;
4. 若存在,首先将第一次出现s时的原始字符串存入结果res,即strs[map[s]],并将map[s]设置为-1(防止下次再存),再将该字符串本身存入结果res;
5. 重复以上1-4步,直到遍历结束。
C++实现代码:
#include<iostream>#include<map>#include<vector>#include<string>#include<algorithm>using namespace std;class Solution {public: vector<string> anagrams(vector<string> &strs) { if(strs.empty()) return vector<string>(); map<string,int> mp; vector<string> ret; size_t i; for(i=0;i<strs.size();i++) { string s=strs[i]; sort(s.begin(),s.end()); //第一次直接插入map中 if(mp.find(s)==mp.end()) { mp[s]=i; } else { //第二次,需要将第一个插入map中的string也放入vector中,以后就不要放了 if(mp[s]>=0) { ret.push_back(strs[mp[s]]); mp[s]=-1; } ret.push_back(strs[i]); } } return ret; }};int main(){ Solution s; vector<string> str={"tea","and","ate","eat","den"}; vector<string> result=s.anagrams(str); for(auto s:result) cout<<s<<" "; cout<<endl;}
运行结果:
Anagrams
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。