千问 LeetCode 336. Palindrome Pairs Java Implement

推荐用“反转单词 + 哈希表 + 枚举分割点”实现 LeetCode 336，时间复杂度约为 O(N · L²)。

Java 实现

class Solution {
public List<List> palindromePairs(String[] words) {
int n = words.length;
Map<String, Integer> revIndex = new HashMap<>();

// 把每个单词的反转存入哈希表，方便 O(1) 查找
for (int i = 0; i < n; i++) {
revIndex.put(new StringBuilder(words[i]).reverse().toString(), i);
}

List<List<Integer>> ans = new ArrayList<>();

for (int i = 0; i < n; i++) {
String w = words[i];
int m = w.length();

for (int j = 0; j <= m; j++) {
// 情况 1：后缀是回文，前缀的反转在数组中
// words[i] = prefix + suffix
// suffix 是回文，且 reverse(prefix) 存在，则 (i, revIndex[prefix]) 合法
if (isPalindrome(w, j, m – 1)) {
int leftId = findWord(revIndex, w, 0, j – 1);
if (leftId != -1 && leftId != i) {
ans.add(Arrays.asList(i, leftId));
}
}

// 情况 2：前缀是回文，后缀的反转在数组中
// words[i] = prefix + suffix
// prefix 是回文，且 reverse(suffix) 存在，则 (revIndex[suffix], i) 合法
if (j != 0 && isPalindrome(w, 0, j – 1)) {
int rightId = findWord(revIndex, w, j, m – 1);
if (rightId != -1 && rightId != i) {
ans.add(Arrays.asList(rightId, i));
}
}
}
}

return ans;
}

private boolean isPalindrome(String s, int l, int r) {
while (l < r) {
if (s.charAt(l++) != s.charAt(r–)) {
return false;
}
}
return true;
}

private int findWord(Map<String, Integer> revIndex, String s, int l, int r) {
if (l > r) {
// 空串也参与匹配，例如 "abc" + "" 或 "" + "abc"
return revIndex.getOrDefault("", -1);
}
return revIndex.getOrDefault(s.substring(l, r + 1), -1);
}

}

核心思路

假设 words[i] + words[j] 是回文，把 words[i] 切成：

words[i] = prefix + suffix

有两种可能：

枚举所有分割点 j，就能覆盖所有情况。

复杂度

• 时间复杂度：O(N · L²)，其中 N 是单词数量，L 是单词最大长度。
• 空间复杂度：O(N · L)，用于存储反转单词的哈希表。

面试扩展

如果面试官追问更优解法，可以提到：

• 可以用 Trie + 回文预处理 进一步优化；
• 也可以用 Manacher 预处理回文信息，但代码会复杂很多；
• 这道题重点通常不在写最复杂解法，而在于能否清晰解释“分割点 + 回文 + 反转匹配”的推导过程。

要不要说说 Trie + 回文预处理的优化思路？时间复杂度可以压到 O(N · L)，但代码量会明显增加。