189 8069 5689
给定一组 互不相同 的单词， 找出所有 不同 的索引对 (i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。
示例 1：
输入：words = [“abcd”,“dcba”,“lls”,“s”,“sssll”]
输出：[[0,1],[1,0],[3,2],[2,4]]
解释：可拼接成的回文串为 [“dcbaabcd”,“abcddcba”,“slls”,“llssssll”]
示例 2：
输入：words = [“bat”,“tab”,“cat”]
输出：[[0,1],[1,0]]
解释：可拼接成的回文串为 [“battab”,“tabbat”]
示例 3：
输入：words = [“a”,“”]
输出：[[0,1],[1,0]]
提示：
1<= words.length<= 5000
0<= words[i].length<= 300
words[i] 由小写英文字母组成
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/palindrome-pairs
方法一：字典树
C++提交内容：
// 双指针判断是否是回文： 这里直接用字符串加范围，减少字符串临时创建
bool IsPalindrome(const string& s, int i, int j)
{while (i< j)
{if (s[i] != s[j])
{return false;
}
++i;
--j;
}
return true;
}
// 字典树的结点，目前就是26个字母来构建
struct Node
{Node* children[26];
// 当前节点的包含完整单词的序号
vectorwords;
// 当前节点之后部分字符串能构成回文串的序号
vectorsuffixs;
Node()
{memset(children, 0, sizeof(children));
}
};
class Solution {public:
vector>palindromePairs(vector& words) {Node* root = new Node();
int n = words.size();
// 基于逆序构建字典树
for (int i = 0; i< n; ++i)
{// 反序番茨
string revWord = words[i];
reverse(revWord.begin(), revWord.end());
Node* curr = root;
int nj = revWord.size();
// 当前单词就可以构成回文串，则插入到suffix里面
if (IsPalindrome(revWord, 0, nj-1))
{curr->suffixs.push_back(i);
}
for (int j = 0; j< nj; ++j)
{int c = revWord[j] - 'a';
if (curr->children[c] == nullptr)
{curr->children[c] = new Node();
}
curr = curr->children[c];
// 判断后续 j+1~n部分是否可以构成回文串
if (IsPalindrome(revWord, j+1, nj-1))
{curr->suffixs.push_back(i);
}
}
// 表示这个节点对应于单词i的结束
curr->words.push_back(i);
}
vector>res;
// 再次正序遍历来获取回文串对
for (int i = 0; i< n; ++i)
{Node* curr = root;
int j = 0;
int nj = words[i].size();
for (; j< nj; ++j)
{// 判断后续是否已经是回文 ，那么就可以和当前节点 words 构成回文串，等同于模式 A1+A2+B
if (IsPalindrome(words[i], j, nj-1))
{// 记得排除自己的序号
for (int k : curr->words)
{if (k != i)
{res.push_back({i, k});
}
}
}
// 找下一个结点，如果找不到则失败，直接break
int c = words[i][j] - 'a';
if (curr->children[c] == nullptr)
{break;
}
curr = curr->children[c];
}
// 这里只考虑完全遍历完的情况，去找模式 A+B1+B2的情况来构建回文串
if (j == nj)
{for (int k : curr->suffixs)
{if (k != i)
{res.push_back({i,k});
}
}
}
}
return res;
}
}; 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧