首页 > 代码库 > leetcode Anagrams

leetcode Anagrams

题目:给定一个vector<string>,然后里面有若干个字符串的长度和组成的字母是相同的,找出这些字符串记录并返回。顾名思义,也就是抛弃单一的字符串,单一是指没有和它长度相同并且组成的字母也相同的另一个字符串。原题如下:

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

Note: All inputs will be in lower-case.

思路:

1.先把每个字符串本身拷贝后排序

2.对排序号的字符串进行map映射到整数

3.判断大于等于2的对应字符串的下标i

4.原来的字符串对应的下标就是要记录的答案

class Solution {public:vector<string> anagrams(vector<string> &strs){    vector<string> ans;    vector<string> test = strs; // 赋值到test中,以便对其排序处理    for (int i = 0; i < strs.size(); ++i)    {        sort(test[i].begin(), test[i].end()); // 进行排序    }    map<string, int> tmp;    for (int i = 0; i < strs.size(); ++i)// 在对应的map里++,如果出现两次那对应的值就大于等于2    {        tmp[test[i]]++;    }    for (int i = 0; i < strs.size(); ++i)    {        if (tmp[test[i]] >= 2)            ans.push_back(strs[i]); //如果有大于等于2,就把相应序号,之前strs里对应的字符串记录,而不是记录已经排好序的    }    return ans;}};

学习到了原来sort还可以对string进行排序。

下面这个只在一个for里面实现。其实也是对其进行排序号,如果第一次发现一个词,那么用map的int值记录当前的标号,下一次再来一个词判断是不是之前已经有了相同的词了,如果有并且存的标号大于零,就两个都要输出,并且将标号置小于零,以便下次不会重复输出。

class Solution {public:    vector<string> anagrams(vector<string> &strs) {        map<string,int> m;        vector<string> result;        int len=strs.size();        for(int i=0;i<len;++i)        {            string a=strs[i];            sort(a.begin(),a.end());            if(m.find(a)==m.end())            {                m[a]=i;            }            else            {                int index=m[a];                if(index>=0)                {                    result.push_back(strs[index]);                    m[a]=-1;                }                result.push_back(strs[i]);            }        }        return result;    }};
View Code

 

leetcode Anagrams