首页 > 代码库 > Anagrams

Anagrams

2024-07-25 17:51:21   220人阅读

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


联系
我们