首页 > 代码库 > Anagrams

Anagrams

  这题Leetcode上面的描述不清楚。怎么也得举两个例子吧,不然谁懂?

  题目的意思是,给定一些字符串,比如["abc","cba","bac","abcd"],找出可以通过交换位置获得的所有字符串。那么这个例子中,返回的结果就是["abc","cba","bac"]。题目隐藏了一个假设,也就是只有一组这样的结果。

  理解了题目的意思的话,其实非常简单:遍历字符串,为字符相同的字符串生成一个key,放到map中。key相同的就是可以通过互换字符位置变换而来的。那么key怎么生成呢?最简单的,就是对字符串按照字母表升序进行排序。那么"abc","cba","bac"都对应"abc"这一个key。当然,对map的处理,要进行一些判断来区分第一次访问、已访问等。代码如下:

  

class Solution {public:    vector<string> anagrams(vector<string> &strs) {        map<string,int> posMap;         vector<string> res;        string tmp;                for(int i=0;i<strs.size();i++)        {            tmp=strs[i];            sort(tmp.begin(),tmp.end());            if(posMap.find(tmp)==posMap.end())            {                posMap[tmp]=i;            }            else            {                if(posMap[i]==-1)                {                    res.push_back(strs[i]);                }                else                {                    res.push_back(posMap[tmp]);                    res.push_back(strs[i]);                    posMap[tmp]=-1;                }            }        }        return res;    }};

  这里生成key是用普通的sort方法,复杂度Nlog(N)。由于字符是小写字母,只有26个,因此可以采用计数排序,复杂度可以降到log(N)。(这里的N是指字符数)。