首页 > 代码库 > Anagrams
Anagrams
Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
For example:
Input: ["tea","and","ate","eat","den"]
Output: ["tea","ate","eat"]
anagrams是某个单词打乱其字母顺序形成的新单词，新单词和原单词包含的字母种类相同，每个字母的数目也相同。
因此可以使用哈希表存储单词的原型，没扫描一个单词，如果该单词原型在哈希表中，那么该单词就输出到结果中
1 class Solution { 2 public: 3 typedef unordered_map<string, int> UMP; 4 5 public: 6 vector<string> anagrams(vector<string> &strs) { 7 UMP htable; 8 vector<string> ans; 9 for(int i=0; i<strs.size(); ++i) {10 string str = strs[i];11 sort(str.begin(), str.end()); //排序单词，认为其字典排序为其原型12 UMP::iterator iter = htable.find(str); //在哈希表中查找其原型13 if( iter == htable.end() ) { //找不着，就在哈希表中添加其原型14 htable.insert( make_pair(str, i) );15 }16 else { //找到17 if( iter->second != -1 ) { //如果结果中没有输出推导出原型的单词，则输出18 ans.push_back(strs[iter->second]);19 iter->second = -1;20 }21 ans.push_back(strs[i]); //哈希表中有原型，则输出该单词22 }23 }24 return ans;25 }26 };
Anagrams
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。