【困难】力扣算法题解析LeetCode336：回文对

关注文末推广名片，即可免费获得本题测试源码！

题目来源：LeetCode 336. 回文对

问题抽象： 给定一个由互不相同的单词组成的字符串数组 words，需找出所有满足条件的索引对 (i, j)（i ≠ j），使得拼接字符串 words[i] + words[j] 构成回文串。

1. 核心需求：

   • 索引对需严格无序（(i, j) 与 (j, i) 视为不同对，均需独立检查）；
   • 拼接结果需是严格回文（正序与逆序完全相同，含字符大小写敏感）；
   • 需输出所有有效索引对（非仅数量）。

2. 计算约束：

   • 避免暴力组合（O(n²×L) 不可行，n 为数组长度，L 为单词长度）；
   • 需优化至 O(n×L²) 或更低（如利用字典树或哈希预处理回文片段）；
   • 空间复杂度可放宽至 O(n×L)（存储单词及反转）。

3. 边界处理：

   • 空字符串：空串 "" 与任意回文串拼接仍为回文（如 ["", "aba"] 中 (0,1) 和 (1,0) 均有效）；
   • 单字符回文：单字符本身是回文（如 ["a", "b"] 中 ("a","b") 无效，但 ("a","a") 若存在不同索引则有效）；
   • 长单词限制：单词最大长度 300，数组最大长度 5000。

4. 特殊案例：

   • 输入 ["abcd","dcba","lls","s","sssll"]，输出 [[0,1],[1,0],[3,2],[2,4]]；
   • 输入 ["bat","tab","cat"]，输出 [[0,1],[1,0]]（因 "bat"+"tab"="battab" 回文）；
   • 输入 ["a",""]，输出 [[0,1],[1,0]]（"a"+""="a" 和 ""+"a"="a" 均回文）。

输入：字符串数组 words（0 <= words.length <= 5000，0 <= words[i].length <= 300）
输出：所有有效索引对组成的列表（格式 List[List[int]]）。

解题思路

本题要求在给定单词列表中，找出所有能组成回文对的索引组合。核心思路是利用哈希表存储单词及其索引，然后对每个单词进行拆分，检查其前缀或后缀是否为回文，剩余部分的逆序是否存在于列表中。具体步骤如下：

1. 构建哈希表：存储每个单词及其索引，便于快速查找。
2. 枚举拆分点：对每个单词，枚举所有可能的拆分点（包括空字符串情况），将其拆分为前缀（prefix）和后缀（suffix）。
3. 情况一：若后缀是回文，则检查前缀的逆序是否存在于哈希表中（且非自身），若存在则组成索引对 [当前索引, 逆序索引]。
4. 情况二：若前缀是回文（且非空），则检查后缀的逆序是否存在于哈希表中（且非自身），若存在则组成索引对 [逆序索引, 当前索引]。
5. 去重处理：通过控制拆分点条件（情况二中要求 j > 0），避免重复添加索引对。

时间复杂度为 $O(n\times k^2)$，其中 $n$ 是单词数量，$k$ 是单词平均长度。空间复杂度为 $O(n\times k)$，用于存储哈希表。

代码实现（Java版）🔥点击下载源码

class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        // 构建单词到索引的映射
        Map<String, Integer> wordMap = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            wordMap.put(words[i], i);
        }

        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            int len = word.length();
            
            // 枚举所有拆分点：j 从 0 到 len（包括 len，处理空后缀）
            for (int j = 0; j <= len; j++) {
                // 拆分前缀和后缀
                String prefix = word.substring(0, j);
                String suffix = word.substring(j);
                
                // 情况1：后缀是回文，检查前缀的逆序是否存在
                if (isPalindrome(suffix)) {
                    String reversedPrefix = new StringBuilder(prefix).reverse().toString();
                    if (wordMap.containsKey(reversedPrefix)) {
                        int index = wordMap.get(reversedPrefix);
                        // 避免与自身匹配
                        if (index != i) {
                            result.add(Arrays.asList(i, index));
                        }
                    }
                }
                
                // 情况2：前缀非空且是回文，检查后缀的逆序是否存在
                // j > 0 避免空前缀重复处理，同时确保前缀非空
                if (j > 0 && isPalindrome(prefix)) {
                    String reversedSuffix = new StringBuilder(suffix).reverse().toString();
                    if (wordMap.containsKey(reversedSuffix)) {
                        int index = wordMap.get(reversedSuffix);
                        // 避免与自身匹配
                        if (index != i) {
                            result.add(Arrays.asList(index, i));
                        }
                    }
                }
            }
        }
        return result;
    }

    // 判断字符串是否为回文
    private boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}

代码说明

1. 哈希表构建：wordMap 存储每个单词及其索引，实现 $O(1)$ 时间复杂度的查找。
2. 拆分点枚举：对每个单词，从位置 0 到 len 进行拆分：
   • 情况1：若后缀 suffix 是回文，检查前缀 prefix 的逆序是否在 wordMap 中，若存在且非自身，添加 [i, index]。
   • 情况2：若前缀 prefix 非空且是回文，检查后缀 suffix 的逆序是否在 wordMap 中，若存在且非自身，添加 [index, i]。
3. 回文判断：isPalindrome 方法使用双指针从两端向中间扫描，判断子串是否为回文。
4. 去重机制：
   • 通过 j > 0 避免空前缀在情况2中重复处理。
   • 通过 index != i 避免单词与自身匹配。

提交详情（执行用时、内存消耗）