JoyAI LeetCode.336 回文对 public List＜List＜Integer＞＞ palindromePairs(String[] words)

给你一个字符串数组 words，要求找出所有不同的索引对 (i, j)，使得 words[i] + words[j] 拼接后是一个回文串。

解题思路

关键在于枚举所有可能的拼接方式，并判断结果是否为回文。由于字符串长度和数量有限（最多5000个，每个最多300字符），我们可以用暴力+优化的方式解决。

核心思想：

对于每一对 (i, j)，拼接 words[i] + words[j]，判断是否为回文。
为了提升效率，可以预先对每个单词判断其是否为回文，以及它的反转是否在数组中。
优化点：利用“回文串的前缀/后缀”特性，避免重复拼接。

代码实现（Java）

import java.util.*;
public class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> result = new ArrayList<>();
        Map<String, Integer> wordToIndex = new HashMap<>();
        // 建立单词到索引的映射
        for (int i = 0; i < words.length; i++) {
            wordToIndex.put(words[i], i);
        }
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            String reversed = new StringBuilder(word).reverse().toString();
            // 情况1：word本身是回文，且存在空串，则 (i, j) 和 (j, i) 都合法
            if (word.isEmpty()) {
                for (int j = 0; j < words.length; j++) {
                    if (j != i && isPalindrome(words[j])) {
                        result.add(Arrays.asList(i, j));
                        result.add(Arrays.asList(j, i));
                    }
                }
                continue;
            }
            // 情况2：word的反转在数组中，且不是自己（避免重复）
            if (wordToIndex.containsKey(reversed) && wordToIndex.get(reversed) != i) {
                result.add(Arrays.asList(i, wordToIndex.get(reversed)));
            }
            // 情况3：word的前缀是回文，且后缀的反转在数组中
            for (int k = 1; k < word.length(); k++) {
                String prefix = word.substring(0, k);
                String suffix = word.substring(k);
                if (isPalindrome(prefix)) {
                    String suffixReversed = new StringBuilder(suffix).reverse().toString();
                    if (wordToIndex.containsKey(suffixReversed) && wordToIndex.get(suffixReversed) != i) {
                        result.add(Arrays.asList(wordToIndex.get(suffixReversed), i));
                    }
                }
            }
            // 情况4：word的后缀是回文，且前缀的反转在数组中
            for (int k = 0; k < word.length() - 1; k++) {
                String prefix = word.substring(0, k + 1);
                String suffix = word.substring(k + 1);
                if (isPalindrome(suffix)) {
                    String prefixReversed = new StringBuilder(prefix).reverse().toString();
                    if (wordToIndex.containsKey(prefixReversed) && wordToIndex.get(prefixReversed) != i) {
                        result.add(Arrays.asList(i, wordToIndex.get(prefixReversed)));
                    }
                }
            }
        }
        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;
            left++;
            right--;
        }
        return true;
    }
}