推荐用“反转单词 哈希表 枚举分割点”实现 LeetCode 336时间复杂度约为 O(N · L²)。Java 实现class Solution {public ListList palindromePairs(String[] words) {int n words.length;MapString, Integer revIndex new HashMap();// 把每个单词的反转存入哈希表方便 O(1) 查找 for (int i 0; i n; i) { revIndex.put(new StringBuilder(words[i]).reverse().toString(), i); } ListListInteger 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(MapString, 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有两种可能suffix 是回文那么需要 prefix 的反转存在于数组中即存在某个 words[j] reverse(prefix)。此时 (i, j) 是答案。prefix 是回文那么需要 suffix 的反转存在于数组中即存在某个 words[j] reverse(suffix)。此时 (j, i) 是答案。枚举所有分割点 j就能覆盖所有情况。复杂度时间复杂度O(N · L²)其中 N 是单词数量L 是单词最大长度。空间复杂度O(N · L)用于存储反转单词的哈希表。面试扩展如果面试官追问更优解法可以提到可以用 Trie 回文预处理 进一步优化也可以用 Manacher 预处理回文信息但代码会复杂很多这道题重点通常不在写最复杂解法而在于能否清晰解释“分割点 回文 反转匹配”的推导过程。要不要说说 Trie 回文预处理的优化思路时间复杂度可以压到 O(N · L)但代码量会明显增加。
