（数组）字符串的回文构词法（ anagrams）

题目：https://www.nowcoder.com/practice/e84e273b31e74427b2a977cbfe60eaf4?tpId=46&tqId=29130&tPage=3&rp=3&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking
思路：
- 　　首先简单介绍一下Anagram（回文构词法）。Anagrams是指由颠倒字母顺序组成的单词，比如“dormitory”颠倒字母顺序会变成“dirty room”，“tea”会变成“eat”。回文构词法有一个特点：单词里的字母的种类和数目没有改变，只是改变了字母的排列顺序。
  
  For example:
  
  Input:　　["tea","and","ate","eat","den"]
  
  Output: ["tea","ate","eat"]
- 　　这里的思路比较简单：主要的方法就是利用哈希表来进行存储（将字符串作为索引，字符串的下标作为实值）。对给出的字符串数组一一进行遍历，每次单独的处理一个字符串：
  - 这里有个技巧：可以将每个字符串都按字符大小排序，这样方便查找
  - 如果该字符串不在哈希表中，就将他存储哈希表（字符串的值作为索引，下标作为实值）
  - 如果找到一样的字符串，将该字符串存入res中：并且将与该字符串对应的那个匹配的anagrams字符串也存入res中，给定一个标志不再重复的将她存入res中。

代码

class Solution {

public:

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

        string str;

        map<string, int> map1;

        vector<string> res;

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

            //将每一个字符串单独进行处理,将他们按字符大小进行排序，然后去哈希表中进行排序，然后去哈希表中 匹配是否存在

            //相同的字符，如果找到就将他放入到vector中

            str = strs[i];

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

            if (map1.find(str) == map1.end()){//找到哈希表的结尾也没找到,用该字符串作为哈希表的键，value为下标值

                map1[str] = i;

            }

            else{

                //将第一次出现的anagrams设置一个哈希值，当下一个anagrams出现的时候将第一次出现的那个字符串进入res中

                //并且将他的哈希值置为-1，以后不再进入res

                if (map1[str] >= ){

                    res.push_back(strs[map1[str]]);

                    map1[str] = -;

                }

                //找到相同的   将他放入res

                res.push_back(strs[i]);

            }

        }

        return res;

    }

};

巴特西

（数组）字符串的回文构词法（ anagrams）

最新文章

热门文章