力扣（LeetCode）336. 回文对（2022.12.03）

给定一组 互不相同 的单词， 找出所有 不同 的索引对 (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];
    // 当前节点的包含完整单词的序号
    vector<int> words;
    // 当前节点之后部分字符串能构成回文串的序号
    vector<int> suffixs;

    Node()
    {
        memset(children, 0, sizeof(children));
    }
};

class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& 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<vector<int>> 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115