[Leetcode] Anagrams 颠倒字母构成词

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

Note: All inputs will be in lower-case.

题意：anagrams的意思是回文构词法。回文构词法有一个特点：单词里的字母的种类和数目没有改变，只是改变了字母的排列顺序。如：

Input:　　["tea","and","ate","eat","den"]

Output: ["tea","ate","eat"]

思路：因为回文构词法的单词之间仅仅是字母改变了顺序，那么我们可以先对单词进行排序，然后我们就可以通过两个单词之间是否相等，来判断是否为回文构词法形成的。那么如何来判断两个单词相等，若是拿某个单词和之前的逐个进行比较，那么时间复杂度就很高了，这里用到map，这样查找起来就方便多了。那查找之后怎么办了？对数组中的每一个字符串：

1）若是在map没有找到，则，将其下标存入，以供后面的对比；

2）若是找到了，先将之前的那个字符串和目前的这个，存入res中。

针对第二种情况，就存在一个问题了，如何避免已存入的再次存入？我们可以将之前存入的那个在map中对应的值改为-1（小于0即可），然后加一定的条件判断（若是不加条件判断，则，改为-1就没有意义了）。参考了doc_sgl代码如下：

 class Solution {

 public:

     vector<string> anagrams(vector<string> &strs)

     {

         vector<string> res;

         unordered_map<string,int> anagram;

         for(int i=;i<strs.size();++i)

         {

             string s=strs[i];

             sort(s.begin(),s.end());

             if(anagram.find(s)==anagram.end())

                 anagram[s]=i;

             else

             {

                 if(anagram[s]>=)

                 {

                     res.push_back(strs[anagram[s]]);    //存之前

                     anagram[s]=-;

                 }

                 res.push_back(strs[i]);     //存现在

             }

         }

         return res;

     }

 };

巴特西

[Leetcode] Anagrams 颠倒字母构成词

最新文章

热门文章