//记录word在输入数组的index, 预设值为-1
// 保存word在输入数组的index,这种word满足条件:
// word的后缀在trie里, 剩余部分是回文串(包括空串)。比如abac, c为后缀,剩余部分aba。注意abac是倒着插入(即caba)trie的
list = new ArrayList<>();
childNode = new TrieNode[26];
public void insert(String word, int index) {
for (int i = word.length() - 1; i >= 0; i--) {
if (isPalindrome(word, 0, i)) {
int pos = word.charAt(i) - 'a';
if (curNode.childNode[pos] == null) {
curNode.childNode[pos] = new TrieNode();
curNode = curNode.childNode[pos];
public void search(String word, int index, List<List<Integer>> res) {
for (int i = 0; i < word.length(); i++) {
// curNode.index >= 0 意味着这里有输入数组里的string
// curNode.index != index 说明curNode.index对应的string和index对应的string不同
// 当word[i...word.length() - 1]是回文串时,说明curNode.index对应的string和index对应的string可以连在一起形成回文串
if (curNode.index >= 0 && curNode.index != index && isPalindrome(word, i, word.length() - 1)) {
res.add(Arrays.asList(index, curNode.index));
int pos = word.charAt(i) - 'a';
if (curNode.childNode[pos] == null) {
curNode = curNode.childNode[pos];
// 当word在字符串中找到与它相同的string后, 查看curNode.list里的index, 这些index对应的word都是在curNode后面的substring为回文串
for (int j : curNode.list) {
res.add(Arrays.asList(index, j));
public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> res = new ArrayList<>();
if (words == null || words.length == 0) {
for (int i = 0; i < words.length; i++) {
trie.insert(words[i], i);
for (int i = 0; i < words.length; i++) {
trie.search(words[i], i, res);
public boolean isPalindrome(String word, int start, int end) {
if (word.charAt(start) != word.charAt(end)) {