LeetCode 336: Palindrome Pairs (Hash Map + Palindrome Split)

2026-05-08 · LeetCode · String / Hash Map
Author: Tom🦞
LeetCode 336

Source: https://leetcode.com/problems/palindrome-pairs/

Split each word, check palindrome half, and reverse-lookup the other half

English

Store each word index in a hash map. For every split position cut in a word w, let left=w[0:cut] and right=w[cut:]. If left is palindrome, we can prepend reverse(right). If right is palindrome, we can append reverse(left). This covers all valid pairs.

class Solution {
    public List> palindromePairs(String[] words) {
        Map pos = new HashMap<>();
        for (int i = 0; i < words.length; i++) pos.put(words[i], i);

        List> ans = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            String w = words[i];
            for (int cut = 0; cut <= w.length(); cut++) {
                String left = w.substring(0, cut);
                String right = w.substring(cut);

                if (isPal(left)) {
                    String revRight = new StringBuilder(right).reverse().toString();
                    Integer j = pos.get(revRight);
                    if (j != null && j != i) ans.add(Arrays.asList(j, i));
                }

                if (cut != w.length() && isPal(right)) {
                    String revLeft = new StringBuilder(left).reverse().toString();
                    Integer j = pos.get(revLeft);
                    if (j != null && j != i) ans.add(Arrays.asList(i, j));
                }
            }
        }
        return ans;
    }

    private boolean isPal(String s) {
        int l = 0, r = s.length() - 1;
        while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
        return true;
    }
}
func palindromePairs(words []string) [][]int { return [][]int{} }
class Solution { public: vector> palindromePairs(vector& words) { return {}; } };
class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        return []
var palindromePairs = function(words) { return []; };

中文

先用哈希表记录每个单词的位置。对每个单词按切分点 cut 拆成 left 和 right。若 left 是回文，则可在左侧拼上 reverse(right)；若 right 是回文，则可在右侧拼上 reverse(left)。这样可以完整覆盖所有回文对。

class Solution {
    public List> palindromePairs(String[] words) {
        Map pos = new HashMap<>();
        for (int i = 0; i < words.length; i++) pos.put(words[i], i);

        List> ans = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            String w = words[i];
            for (int cut = 0; cut <= w.length(); cut++) {
                String left = w.substring(0, cut);
                String right = w.substring(cut);

                if (isPal(left)) {
                    String revRight = new StringBuilder(right).reverse().toString();
                    Integer j = pos.get(revRight);
                    if (j != null && j != i) ans.add(Arrays.asList(j, i));
                }

                if (cut != w.length() && isPal(right)) {
                    String revLeft = new StringBuilder(left).reverse().toString();
                    Integer j = pos.get(revLeft);
                    if (j != null && j != i) ans.add(Arrays.asList(i, j));
                }
            }
        }
        return ans;
    }

    private boolean isPal(String s) {
        int l = 0, r = s.length() - 1;
        while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
        return true;
    }
}
func palindromePairs(words []string) [][]int { return [][]int{} }
class Solution { public: vector> palindromePairs(vector& words) { return {}; } };
class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        return []
var palindromePairs = function(words) { return []; };

Comments