336. 回文对
题目描述
输入一个字符串数组 words，其中的字符串两两不同，下标从 0 开始。
如果两个不同下标 i 和 j 满足：把 words[i] 和 words[j] 按这个先后拼接后得到回文串，就称 [i, j] 是一个回文对。注意 [i, j] 和 [j, i] 是两个不同的对，需要分别判断。
返回所有回文对组成的列表，顺序不限。字符串可以是空串。
要求算法的时间复杂度与所有字符串长度之和同阶。
示例 1
输入：words = ["abcd","dcba","lls","s","sssll"] 输出：[[1,0],[0,1],[3,2],[2,4]]
解释：拼接结果分别为 "dcbaabcd"、"abcddcba"、"slls"、"llssssll"，都是回文。
示例 2
输入：words = ["bat","tab","cat"] 输出：[[1,0],[0,1]]
解释："tabbat" 和 "battab" 是回文，"cat" 无法与其他词组成回文。
示例 3
输入：words = ["a",""] 输出：[[0,1],[1,0]]
解释：空串与 "a" 无论哪个在前，拼出来都是 "a"。
数据范围
1 <= words.length <= 50000 <= words[i].length <= 300words[i]只含小写英文字母
解题思路：哈希表枚举拆分点
设 w = words[i]，把 w 在位置 k 切成 pre + suf。① 若 pre 是回文，而 reverse(suf) 也在数组中（下标 j），则 reverse(suf) + pre + suf 是回文，得到 [j, i]。② 若 suf 是回文，而 reverse(pre) 在数组中，则 pre + suf + reverse(pre) 是回文，得到 [i, j]。用哈希表记下每个单词的下标，枚举所有切分点即可。
为什么正确
两个单词拼成回文时，较长的那个多出来的部分必须自身是回文，其余部分必须是另一个单词的反转，所以每个合法的对都会在较长单词的某个切分点被找到。
复杂度分析
时间 O(n · L²)，n 为单词数，L 为最大长度；空间 O(n · L)。
易错点
空串与任何回文单词都能配成两个对；为避免同一对被两个情况重复统计，情况 ② 要排除 k = len(w)（此时它与情况 ① 的 k = 0 对称）。还要排除 j = i 的自己配自己。暴力枚举所有对是 O(n² · L)，n = 5000 时会超时。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def palindromePairs(self, words: List[str]) -> List[List[int]]:
d = {w: i for i, w in enumerate(words)}
res = []
for i, w in enumerate(words):
for k in range(len(w) + 1):
pre, suf = w[:k], w[k:]
if pre == pre[::-1] and suf[::-1] in d and d[suf[::-1]] != i:
res.append([d[suf[::-1]], i])
if k != len(w) and suf == suf[::-1] and pre[::-1] in d and d[pre[::-1]] != i:
res.append([i, d[pre[::-1]]])
return resclass Solution {
private boolean isPal(String s, int l, int r) {
while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
return true;
}
public List<List<Integer>> palindromePairs(String[] words) {
Map<String, Integer> d = new HashMap<>();
for (int i = 0; i < words.length; i++) d.put(words[i], i);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < words.length; i++) {
String w = words[i];
int m = w.length();
for (int k = 0; k <= m; k++) {
String preR = new StringBuilder(w.substring(0, k)).reverse().toString();
String sufR = new StringBuilder(w.substring(k)).reverse().toString();
if (isPal(w, 0, k - 1)) {
Integer j = d.get(sufR);
if (j != null && j != i) res.add(Arrays.asList(j, i));
}
if (k != m && isPal(w, k, m - 1)) {
Integer j = d.get(preR);
if (j != null && j != i) res.add(Arrays.asList(i, j));
}
}
}
return res;
}
}class Solution {
bool isPal(const string& s, int l, int r) {
while (l < r) if (s[l++] != s[r--]) return false;
return true;
}
public:
vector<vector<int>> palindromePairs(vector<string>& words) {
unordered_map<string, int> d;
for (int i = 0; i < (int)words.size(); i++) d[words[i]] = i;
vector<vector<int>> res;
for (int i = 0; i < (int)words.size(); i++) {
const string& w = words[i];
int m = w.size();
for (int k = 0; k <= m; k++) {
string preR(w.rend() - k, w.rend());
string sufR(w.rbegin(), w.rend() - k);
if (isPal(w, 0, k - 1)) {
auto it = d.find(sufR);
if (it != d.end() && it->second != i) res.push_back({it->second, i});
}
if (k != m && isPal(w, k, m - 1)) {
auto it = d.find(preR);
if (it != d.end() && it->second != i) res.push_back({i, it->second});
}
}
}
return res;
}
};func isPal336(s string, l, r int) bool {
for l < r {
if s[l] != s[r] {
return false
}
l++
r--
}
return true
}
func rev336(s string) string {
b := []byte(s)
for l, r := 0, len(b)-1; l < r; l, r = l+1, r-1 {
b[l], b[r] = b[r], b[l]
}
return string(b)
}
func palindromePairs(words []string) [][]int {
d := map[string]int{}
for i, w := range words {
d[w] = i
}
res := [][]int{}
for i, w := range words {
m := len(w)
for k := 0; k <= m; k++ {
preR, sufR := rev336(w[:k]), rev336(w[k:])
if isPal336(w, 0, k-1) {
if j, ok := d[sufR]; ok && j != i {
res = append(res, []int{j, i})
}
}
if k != m && isPal336(w, k, m-1) {
if j, ok := d[preR]; ok && j != i {
res = append(res, []int{i, j})
}
}
}
}
return res
}var palindromePairs = function(words) {
const isPal = (s, l, r) => { while (l < r) if (s[l++] !== s[r--]) return false; return true; };
const rev = s => s.split('').reverse().join('');
const d = new Map();
words.forEach((w, i) => d.set(w, i));
const res = [];
for (let i = 0; i < words.length; i++) {
const w = words[i], m = w.length;
for (let k = 0; k <= m; k++) {
const preR = rev(w.slice(0, k)), sufR = rev(w.slice(k));
if (isPal(w, 0, k - 1) && d.has(sufR) && d.get(sufR) !== i) {
res.push([d.get(sufR), i]);
}
if (k !== m && isPal(w, k, m - 1) && d.has(preR) && d.get(preR) !== i) {
res.push([i, d.get(preR)]);
}
}
}
return res;
};function palindromePairs(words: string[]): number[][] {
const isPal = (s: string, l: number, r: number): boolean => { while (l < r) if (s[l++] !== s[r--]) return false; return true; };
const rev = (s: string): string => s.split('').reverse().join('');
const d = new Map<string, number>();
words.forEach((w, i) => d.set(w, i));
const res: number[][] = [];
for (let i = 0; i < words.length; i++) {
const w = words[i], m = w.length;
for (let k = 0; k <= m; k++) {
const preR = rev(w.slice(0, k)), sufR = rev(w.slice(k));
if (isPal(w, 0, k - 1) && d.has(sufR) && d.get(sufR) !== i) {
res.push([d.get(sufR)!, i]);
}
if (k !== m && isPal(w, k, m - 1) && d.has(preR) && d.get(preR) !== i) {
res.push([i, d.get(preR)!]);
}
}
}
return res;
}其他解法
两种方法都枚举拆分点并检查另一半是否为回文：哈希表版用子串查表，字典树版把“查反转前缀”变成沿树前进。
解法 2：字典树（存反转单词） 时间 O(n·L²)，空间 O(n·L)
把每个单词反转后插入字典树。插入时，如果反转串从当前位置到末尾是回文，就把单词下标记入当前节点的 pal 列表；结束节点记录 idx 并也加入 pal。查询单词 w 时沿字典树前进：途中遇到 idx，且 w 剩余部分是回文，就得到一对；w 走完后，当前节点 pal 列表里的单词都能接在 w 后面。
查询时一边走一边匹配，不用为每个拆分点生成子串并求哈希。代码更长，节点数组占内存更多。
class Solution:
def palindromePairs(self, words: List[str]) -> List[List[int]]:
def is_pal(s, l, r):
while l < r:
if s[l] != s[r]:
return False
l += 1
r -= 1
return True
children = [[0] * 26]
idx = [-1]
pal = [[]]
for j, w in enumerate(words):
r = w[::-1]
node = 0
for p, ch in enumerate(r):
if is_pal(r, p, len(r) - 1):
pal[node].append(j)
c = ord(ch) - 97
if not children[node][c]:
children[node][c] = len(children)
children.append([0] * 26)
idx.append(-1)
pal.append([])
node = children[node][c]
idx[node] = j
pal[node].append(j)
res = []
for i, w in enumerate(words):
node = 0
ok = True
for p, ch in enumerate(w):
if idx[node] >= 0 and is_pal(w, p, len(w) - 1):
res.append([i, idx[node]])
node = children[node][ord(ch) - 97]
if not node:
ok = False
break
if ok:
for j in pal[node]:
if j != i:
res.append([i, j])
return resclass Solution {
private boolean isPal(String s, int l, int r) {
while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
return true;
}
public List<List<Integer>> palindromePairs(String[] words) {
List<int[]> children = new ArrayList<>();
List<Integer> idx = new ArrayList<>();
List<List<Integer>> pal = new ArrayList<>();
children.add(new int[26]);
idx.add(-1);
pal.add(new ArrayList<>());
for (int j = 0; j < words.length; j++) {
String r = new StringBuilder(words[j]).reverse().toString();
int node = 0, len = r.length();
for (int p = 0; p < len; p++) {
if (isPal(r, p, len - 1)) pal.get(node).add(j);
int c = r.charAt(p) - 'a';
if (children.get(node)[c] == 0) {
children.get(node)[c] = children.size();
children.add(new int[26]);
idx.add(-1);
pal.add(new ArrayList<>());
}
node = children.get(node)[c];
}
idx.set(node, j);
pal.get(node).add(j);
}
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < words.length; i++) {
String w = words[i];
int node = 0, len = w.length();
boolean ok = true;
for (int p = 0; p < len; p++) {
if (idx.get(node) >= 0 && isPal(w, p, len - 1)) res.add(Arrays.asList(i, idx.get(node)));
node = children.get(node)[w.charAt(p) - 'a'];
if (node == 0) { ok = false; break; }
}
if (ok) {
for (int j : pal.get(node)) if (j != i) res.add(Arrays.asList(i, j));
}
}
return res;
}
}class Solution {
bool isPal(const string& s, int l, int r) {
while (l < r) if (s[l++] != s[r--]) return false;
return true;
}
public:
vector<vector<int>> palindromePairs(vector<string>& words) {
vector<array<int, 26>> children(1);
children[0].fill(0);
vector<int> idx(1, -1);
vector<vector<int>> pal(1);
for (int j = 0; j < (int)words.size(); j++) {
string r(words[j].rbegin(), words[j].rend());
int node = 0, len = r.size();
for (int p = 0; p < len; p++) {
if (isPal(r, p, len - 1)) pal[node].push_back(j);
int c = r[p] - 'a';
if (!children[node][c]) {
children[node][c] = children.size();
children.emplace_back();
children.back().fill(0);
idx.push_back(-1);
pal.emplace_back();
}
node = children[node][c];
}
idx[node] = j;
pal[node].push_back(j);
}
vector<vector<int>> res;
for (int i = 0; i < (int)words.size(); i++) {
const string& w = words[i];
int node = 0, len = w.size();
bool ok = true;
for (int p = 0; p < len; p++) {
if (idx[node] >= 0 && isPal(w, p, len - 1)) res.push_back({i, idx[node]});
node = children[node][w[p] - 'a'];
if (!node) { ok = false; break; }
}
if (ok) {
for (int j : pal[node]) if (j != i) res.push_back({i, j});
}
}
return res;
}
};func isPal336t(s string, l, r int) bool {
for l < r {
if s[l] != s[r] {
return false
}
l++
r--
}
return true
}
func palindromePairs(words []string) [][]int {
children := [][26]int{{}}
idx := []int{-1}
pal := [][]int{{}}
for j, w := range words {
b := []byte(w)
for l, r := 0, len(b)-1; l < r; l, r = l+1, r-1 {
b[l], b[r] = b[r], b[l]
}
r := string(b)
node := 0
for p := 0; p < len(r); p++ {
if isPal336t(r, p, len(r)-1) {
pal[node] = append(pal[node], j)
}
c := r[p] - 'a'
if children[node][c] == 0 {
children[node][c] = len(children)
children = append(children, [26]int{})
idx = append(idx, -1)
pal = append(pal, []int{})
}
node = children[node][c]
}
idx[node] = j
pal[node] = append(pal[node], j)
}
res := [][]int{}
for i, w := range words {
node := 0
ok := true
for p := 0; p < len(w); p++ {
if idx[node] >= 0 && isPal336t(w, p, len(w)-1) {
res = append(res, []int{i, idx[node]})
}
node = children[node][w[p]-'a']
if node == 0 {
ok = false
break
}
}
if ok {
for _, j := range pal[node] {
if j != i {
res = append(res, []int{i, j})
}
}
}
}
return res
}var palindromePairs = function(words) {
const isPal = (s, l, r) => { while (l < r) if (s[l++] !== s[r--]) return false; return true; };
const children = [new Array(26).fill(0)];
const idx = [-1];
const pal = [[]];
for (let j = 0; j < words.length; j++) {
const r = words[j].split('').reverse().join('');
let node = 0;
for (let p = 0; p < r.length; p++) {
if (isPal(r, p, r.length - 1)) pal[node].push(j);
const c = r.charCodeAt(p) - 97;
if (!children[node][c]) {
children[node][c] = children.length;
children.push(new Array(26).fill(0));
idx.push(-1);
pal.push([]);
}
node = children[node][c];
}
idx[node] = j;
pal[node].push(j);
}
const res = [];
for (let i = 0; i < words.length; i++) {
const w = words[i];
let node = 0, ok = true;
for (let p = 0; p < w.length; p++) {
if (idx[node] >= 0 && isPal(w, p, w.length - 1)) res.push([i, idx[node]]);
node = children[node][w.charCodeAt(p) - 97];
if (!node) { ok = false; break; }
}
if (ok) {
for (const j of pal[node]) if (j !== i) res.push([i, j]);
}
}
return res;
};function palindromePairs(words: string[]): number[][] {
const isPal = (s: string, l: number, r: number): boolean => { while (l < r) if (s[l++] !== s[r--]) return false; return true; };
const children: number[][] = [new Array(26).fill(0)];
const idx: number[] = [-1];
const pal: number[][] = [[]];
for (let j = 0; j < words.length; j++) {
const r = words[j].split('').reverse().join('');
let node = 0;
for (let p = 0; p < r.length; p++) {
if (isPal(r, p, r.length - 1)) pal[node].push(j);
const c = r.charCodeAt(p) - 97;
if (!children[node][c]) {
children[node][c] = children.length;
children.push(new Array(26).fill(0));
idx.push(-1);
pal.push([]);
}
node = children[node][c];
}
idx[node] = j;
pal[node].push(j);
}
const res: number[][] = [];
for (let i = 0; i < words.length; i++) {
const w = words[i];
let node = 0, ok = true;
for (let p = 0; p < w.length; p++) {
if (idx[node] >= 0 && isPal(w, p, w.length - 1)) res.push([i, idx[node]]);
node = children[node][w.charCodeAt(p) - 97];
if (!node) { ok = false; break; }
}
if (ok) {
for (const j of pal[node]) if (j !== i) res.push([i, j]);
}
}
return res;
}