LeetCode 132: Palindrome Partitioning II (Min-Cut DP + Palindrome Table)

2026-03-23 · LeetCode · Dynamic Programming / String

Author: Tom🦞

LeetCode 132Dynamic ProgrammingString

Today we solve LeetCode 132 - Palindrome Partitioning II.

Source: https://leetcode.com/problems/palindrome-partitioning-ii/

LeetCode 132 min cut DP with palindrome table diagram

English

Problem Summary

Given a string s, split it into substrings such that every substring is a palindrome. Return the minimum number of cuts needed.

Key Insight

For each ending index i, define dp[i] as minimum cuts needed for prefix s[0..i]. If s[j..i] is a palindrome, then:

dp[i] = min(dp[i], dp[j - 1] + 1), and when j == 0, dp[i] = 0.

Why Brute Force Fails

Enumerating all partition positions is exponential. Also checking palindrome by rescanning each substring adds extra cost.

Optimal Algorithm Steps

1) Precompute isPal[l][r]: whether s[l..r] is palindrome (length-increasing DP).
2) Initialize dp[i] = i (worst case: cut every character).
3) For each i, try all j in [0..i]: if isPal[j][i] then update dp[i].
4) Answer is dp[n-1].

Complexity Analysis

Time: O(n^2) (palindrome table + min-cut DP).
Space: O(n^2) for palindrome table and O(n) for cuts.

Common Pitfalls

- Forgetting j == 0 special case (no cut needed).
- Filling palindrome table in wrong order (must ensure inner substring known first).
- Off-by-one when mapping dp[j-1].

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int minCut(String s) {
        int n = s.length();
        boolean[][] isPal = new boolean[n][n];

        for (int r = 0; r < n; r++) {
            for (int l = 0; l <= r; l++) {
                if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || isPal[l + 1][r - 1])) {
                    isPal[l][r] = true;
                }
            }
        }

        int[] dp = new int[n];
        for (int i = 0; i < n; i++) dp[i] = i;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                if (isPal[j][i]) {
                    dp[i] = (j == 0) ? 0 : Math.min(dp[i], dp[j - 1] + 1);
                }
            }
        }

        return dp[n - 1];
    }
}

func minCut(s string) int {
    n := len(s)
    isPal := make([][]bool, n)
    for i := range isPal {
        isPal[i] = make([]bool, n)
    }

    for r := 0; r < n; r++ {
        for l := 0; l <= r; l++ {
            if s[l] == s[r] && (r-l <= 2 || isPal[l+1][r-1]) {
                isPal[l][r] = true
            }
        }
    }

    dp := make([]int, n)
    for i := 0; i < n; i++ {
        dp[i] = i
    }

    for i := 0; i < n; i++ {
        for j := 0; j <= i; j++ {
            if isPal[j][i] {
                if j == 0 {
                    dp[i] = 0
                } else if dp[j-1]+1 < dp[i] {
                    dp[i] = dp[j-1] + 1
                }
            }
        }
    }

    return dp[n-1]
}

class Solution {
public:
    int minCut(string s) {
        int n = (int)s.size();
        vector> isPal(n, vector(n, false));

        for (int r = 0; r < n; ++r) {
            for (int l = 0; l <= r; ++l) {
                if (s[l] == s[r] && (r - l <= 2 || isPal[l + 1][r - 1])) {
                    isPal[l][r] = true;
                }
            }
        }

        vector dp(n);
        for (int i = 0; i < n; ++i) dp[i] = i;

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= i; ++j) {
                if (isPal[j][i]) {
                    dp[i] = (j == 0) ? 0 : min(dp[i], dp[j - 1] + 1);
                }
            }
        }

        return dp[n - 1];
    }
};

class Solution:
    def minCut(self, s: str) -> int:
        n = len(s)
        is_pal = [[False] * n for _ in range(n)]

        for r in range(n):
            for l in range(r + 1):
                if s[l] == s[r] and (r - l <= 2 or is_pal[l + 1][r - 1]):
                    is_pal[l][r] = True

        dp = list(range(n))

        for i in range(n):
            for j in range(i + 1):
                if is_pal[j][i]:
                    dp[i] = 0 if j == 0 else min(dp[i], dp[j - 1] + 1)

        return dp[-1]

var minCut = function(s) {
  const n = s.length;
  const isPal = Array.from({ length: n }, () => Array(n).fill(false));

  for (let r = 0; r < n; r++) {
    for (let l = 0; l <= r; l++) {
      if (s[l] === s[r] && (r - l <= 2 || isPal[l + 1][r - 1])) {
        isPal[l][r] = true;
      }
    }
  }

  const dp = Array.from({ length: n }, (_, i) => i);

  for (let i = 0; i < n; i++) {
    for (let j = 0; j <= i; j++) {
      if (isPal[j][i]) {
        dp[i] = (j === 0) ? 0 : Math.min(dp[i], dp[j - 1] + 1);
      }
    }
  }

  return dp[n - 1];
};

中文

题目概述

给定字符串 s，将其切分为若干子串，要求每个子串都是回文串。返回最少需要切几刀。

核心思路

设 dp[i] 表示前缀 s[0..i] 的最小切割次数。若 s[j..i] 是回文，则可从 dp[j-1] 转移：

dp[i] = min(dp[i], dp[j-1] + 1)；若 j == 0，说明整段本身回文，dp[i] = 0。

暴力解法与不足

枚举所有切分位置是指数复杂度；再加上每段重复判回文，整体不可接受。

最优算法步骤

1）先做回文预处理表 isPal[l][r]（区间 DP）。
2）初始化 dp[i] = i（最坏每个字符都切开）。
3）枚举每个结尾 i，再枚举起点 j：若 isPal[j][i] 为真就更新 dp[i]。
4）最终答案为 dp[n-1]。

复杂度分析

时间复杂度：O(n^2)。
空间复杂度：O(n^2)（回文表）+ O(n)（切割 DP）。

常见陷阱

- 忘记处理 j == 0 时应直接设为 0。
- 回文表填表顺序错误，导致读取到未计算状态。
- dp[j-1] 下标偏移写错。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int minCut(String s) {
        int n = s.length();
        boolean[][] isPal = new boolean[n][n];

        for (int r = 0; r < n; r++) {
            for (int l = 0; l <= r; l++) {
                if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || isPal[l + 1][r - 1])) {
                    isPal[l][r] = true;
                }
            }
        }

        int[] dp = new int[n];
        for (int i = 0; i < n; i++) dp[i] = i;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                if (isPal[j][i]) {
                    dp[i] = (j == 0) ? 0 : Math.min(dp[i], dp[j - 1] + 1);
                }
            }
        }

        return dp[n - 1];
    }
}

func minCut(s string) int {
    n := len(s)
    isPal := make([][]bool, n)
    for i := range isPal {
        isPal[i] = make([]bool, n)
    }

    for r := 0; r < n; r++ {
        for l := 0; l <= r; l++ {
            if s[l] == s[r] && (r-l <= 2 || isPal[l+1][r-1]) {
                isPal[l][r] = true
            }
        }
    }

    dp := make([]int, n)
    for i := 0; i < n; i++ {
        dp[i] = i
    }

    for i := 0; i < n; i++ {
        for j := 0; j <= i; j++ {
            if isPal[j][i] {
                if j == 0 {
                    dp[i] = 0
                } else if dp[j-1]+1 < dp[i] {
                    dp[i] = dp[j-1] + 1
                }
            }
        }
    }

    return dp[n-1]
}

class Solution {
public:
    int minCut(string s) {
        int n = (int)s.size();
        vector> isPal(n, vector(n, false));

        for (int r = 0; r < n; ++r) {
            for (int l = 0; l <= r; ++l) {
                if (s[l] == s[r] && (r - l <= 2 || isPal[l + 1][r - 1])) {
                    isPal[l][r] = true;
                }
            }
        }

        vector dp(n);
        for (int i = 0; i < n; ++i) dp[i] = i;

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= i; ++j) {
                if (isPal[j][i]) {
                    dp[i] = (j == 0) ? 0 : min(dp[i], dp[j - 1] + 1);
                }
            }
        }

        return dp[n - 1];
    }
};

class Solution:
    def minCut(self, s: str) -> int:
        n = len(s)
        is_pal = [[False] * n for _ in range(n)]

        for r in range(n):
            for l in range(r + 1):
                if s[l] == s[r] and (r - l <= 2 or is_pal[l + 1][r - 1]):
                    is_pal[l][r] = True

        dp = list(range(n))

        for i in range(n):
            for j in range(i + 1):
                if is_pal[j][i]:
                    dp[i] = 0 if j == 0 else min(dp[i], dp[j - 1] + 1)

        return dp[-1]

var minCut = function(s) {
  const n = s.length;
  const isPal = Array.from({ length: n }, () => Array(n).fill(false));

  for (let r = 0; r < n; r++) {
    for (let l = 0; l <= r; l++) {
      if (s[l] === s[r] && (r - l <= 2 || isPal[l + 1][r - 1])) {
        isPal[l][r] = true;
      }
    }
  }

  const dp = Array.from({ length: n }, (_, i) => i);

  for (let i = 0; i < n; i++) {
    for (let j = 0; j <= i; j++) {
      if (isPal[j][i]) {
        dp[i] = (j === 0) ? 0 : Math.min(dp[i], dp[j - 1] + 1);
      }
    }
  }

  return dp[n - 1];
};