方法一：

首先使用暴力解法：

两层循环，拼接字符串

判断字符串是不是回文 ```cpp class PalindromePairs { public: vector> palindromePairs(vector& words) {

  vector<vector<int>> ans;
  for(int i = 0; i < words.size(); i++){
      for(int j = 0; j < words.size(); j++){
          if(i == j) continue;
          bool isPal = isPalindrome(_temp);
          if(isPalindrome(words[i] + words[j])){
              vector<int> _ans;
              _ans.push_back(i);
              _ans.push_back(j);
              ans.push_back(_ans);
          }
      }
  }
  return ans;

}

bool isPalindrome(string s) {

  int start = 0;
  int end = s.size() - 1;
  for(int i = 0; i < s.size(); i++){
      while (start < end){
          if(s[start] == s[end]){
              start ++;
              end --;
          } else {
              return false;
          }
      }
  }
  return true;

} };


<a name="pa7Wa"></a>
# 方法二：字典数
![image.png](https://cdn.nlark.com/yuque/0/2020/png/162542/1596874731141-e78cc316-d14b-40a2-8d27-05ffeef0c2bb.png#align=left&display=inline&height=163&margin=%5Bobject%20Object%5D&name=image.png&originHeight=325&originWidth=388&size=43343&status=done&style=none&width=194)
<a name="wE5GB"></a>
## 什么是字典树：
又称单词查找树，[Trie树](https://baike.baidu.com/item/Trie%E6%A0%91)，是一种[树形结构](https://baike.baidu.com/item/%E6%A0%91%E5%BD%A2%E7%BB%93%E6%9E%84/9663807)，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的[字符](https://baike.baidu.com/item/%E5%AD%97%E7%AC%A6)串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

<a name="ad27ca8d"></a>
## 字典树的特性：
根节点不包含字符，除根节点外每一个节点都只包含一个字符； 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串； 每个节点的所有子节点包含的字符都不相同。<br />

<a name="Seoib"></a>
## 应用：
<a name="wTCuG"></a>
### 串的快速检索
给出N个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。<br />在这道题中，我们可以用[数组](https://baike.baidu.com/item/%E6%95%B0%E7%BB%84)枚举，用哈希，用字典树，先把熟词建一棵树，然后读入文章进行比较，这种方法效率是比较高的。<br />
<a name="gUeWU"></a>
### “串”排序
给定N个互不相同的仅由一个单词构成的英文名，让你将他们按[字典序](https://baike.baidu.com/item/%E5%AD%97%E5%85%B8%E5%BA%8F)从小到大输出<br />用字典树进行排序，采用[数组](https://baike.baidu.com/item/%E6%95%B0%E7%BB%84)的方式创建字典树，这棵树的每个结点的所有儿子很显然地按照其字母大小排序。对这棵树进行先序遍历即可。<br />
<a name="1QtBc"></a>
### 最长公共前缀
对所有串建立字典树，对于两个串的最长公共前缀的长度即他们所在的结点的公共祖先个数，于是，问题就转化为当时公共祖先问题。

<a name="Mmt0D"></a>
## 本题题解
本题的两个字符串可以分为三种情况（s1 是第一个字符串，s2 是第二个字符串）

- s1 的长度等于 s2 的长度 => 两个字符串是否是回文字符串
- s1 的长度大于 s2 的长度 => 那么 `s1[0, s2.size() - 1]`  要是 s2 的倒序， `s1[s2.size() -1, s1.size() -1 ]` 要是一个回文数，才符合题目要求；
- s1 的长度小于 s2 的长度，和上一种情况相反；

![image.png](https://cdn.nlark.com/yuque/0/2020/png/162542/1596875071926-244e0cb5-9bdc-40f5-846b-d8c78019cd23.png#align=left&display=inline&height=182&margin=%5Bobject%20Object%5D&name=image.png&originHeight=363&originWidth=759&size=92048&status=done&style=none&width=379.5)

那么

- 构建一个字典树，保存所有逆序字符串
- 遍历 words
   - 对每一个单词进行遍历，能否分割成两个字符串，
      - 一个字符串可以构成回文
      - 剩下的另一个字符串的倒序可以在字典中找到。
   - 要注意两个字符串的顺便
   - 其中回文的字符串可以为空

```cpp
//字典树节点
class TrieNode
{
private:
    bool isEnd;//单词结束标记
    int index;//单词序号
    vector<TrieNode*> children;//子节点
public:
    //构造
    TrieNode():index(-1),isEnd(false),children(26,nullptr){}
    //析构
    ~TrieNode()
    {
        for(int i = 0;i < 26;i++)
        {
            if( children[i]) 
            {
                delete children[i];
                children[i] = nullptr;
            }
        }
    }
    //对外接口
    int getIndex() { return index;}
    void setIndex( int i) { index = i;}
    bool isWordEnd() { return isEnd;}
    void SetEnd(){ isEnd = true ;}
    //插入一个字符到子节点
    TrieNode * insertNode(char c)
    {
        if( !( 'a' <= c &&  c <= 'z')) return nullptr;
        int id = c-'a';
        if( children[id] == nullptr)
        {
            children[id] = new TrieNode();

        }
        return children[id];
    }
    //在子节点中查找一个字符
    TrieNode * getNode(char c)
    {
         if( !( 'a' <= c && c <= 'z')) return nullptr;
         int id = c-'a';
         return children[id] ;
    }
};

//字典树
class Trie
{
private:
    TrieNode * root;//根节点
public:
    Trie():root(new TrieNode()){}
    ~Trie()  { delete root;}  
    //插入一个单词及序号
    void insert( string word,int index)
    {
        TrieNode * p = root;
        for( int i = 0;i<word.size();i++)
        {
            p = p->insertNode(word[i]);
        }
        p->SetEnd();
        p->setIndex(index);
    }
    //查找一个字符串
    TrieNode *getNode(string word)
    {
        TrieNode * p = root;
        for(int i = 0;i < word.size();i++ )
        {
            p = p->getNode(word[i]) ;
            if( p == NULL ) return NULL;
        }
        return p;
    }
    //查找一个单词，返回序号
    bool  search(string word,int  &index)
    {

        TrieNode * p = getNode(word);
        if( p )
        {
            index = p->getIndex();
            return  p->isWordEnd();
        }
        return false;
    }


};
class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        vector<vector<int>> res;
        //构建字典树
        Trie * trieTree = new Trie();
        for(int i = 0;i < words.size();i++)
        {
            trieTree->insert(words[i],i);
        }
        for(int i = 0;i < words.size();i++)
        {
            for(int j = 0;j < words[i].size();j++ )
            {
                bool flag = check(words[i],0,j);
                if(flag)//前半截是回文
                {
                    string temp = words[i].substr(j+1);
                    reverse(temp.begin(),temp.end());
                    int index = -1;
                    if( trieTree->search(temp,index) )
                    {
                        if( i != index  )
                        {
                             res.push_back({index,i});
                             if( temp == "")
                             {
                                 res.push_back({i,index});
                             }
                        }

                    }
                }
                flag = check(words[i],j+1,words[i].size()-1);
                if(flag)//后半截是回文
                {
                        string temp = words[i].substr(0,j+1);
                        reverse(temp.begin(),temp.end());
                        int index = -1;
                        if( trieTree->search(temp,index) )
                        {
                            if( i != index  )
                                res.push_back({i,index});
                        }
                }    
            }
        }
        return res;
    }
    bool check(string &vec,int left,int right)
    {
        int i = left;
        int j = right;
        while(i <= j)
        {
            if( vec[i] != vec[j]) return false;
            i++;
            j--;
        }
        return true;
    }
};

【0806】回文对

方法一：