Skip to content

132. Palindrome Partitioning II 👍

  • Time: $O(mn)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
 public:
  int minCut(string s) {
    const int n = s.length();
    // isPalindrome[i][j] := true if s[i..j] is a palindrome
    vector<vector<bool>> isPalindrome(n, vector<bool>(n, true));
    // dp[i] := the minimum cuts needed for a palindrome partitioning of s[0..i]
    vector<int> dp(n, n);

    for (int l = 2; l <= n; ++l)
      for (int i = 0, j = l - 1; j < n; ++i, ++j)
        isPalindrome[i][j] = s[i] == s[j] && isPalindrome[i + 1][j - 1];

    for (int i = 0; i < n; ++i) {
      if (isPalindrome[0][i]) {
        dp[i] = 0;
        continue;
      }

      // Try all the possible partitions.
      for (int j = 0; j < i; ++j)
        if (isPalindrome[j + 1][i])
          dp[i] = min(dp[i], dp[j] + 1);
    }

    return dp.back();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
  public int minCut(String s) {
    final int n = s.length();
    // isPalindrome[i][j] := true if s[i..j] is a palindrome
    boolean[][] isPalindrome = new boolean[n][n];
    for (boolean[] row : isPalindrome)
      Arrays.fill(row, true);
    // dp[i] := the minimum cuts needed for a palindrome partitioning of s[0..i]
    int[] dp = new int[n];
    Arrays.fill(dp, n);

    for (int l = 2; l <= n; ++l)
      for (int i = 0, j = l - 1; j < n; ++i, ++j)
        isPalindrome[i][j] = s.charAt(i) == s.charAt(j) && isPalindrome[i + 1][j - 1];

    for (int i = 0; i < n; ++i) {
      if (isPalindrome[0][i]) {
        dp[i] = 0;
        continue;
      }

      // Try all the possible partitions.
      for (int j = 0; j < i; ++j)
        if (isPalindrome[j + 1][i])
          dp[i] = Math.min(dp[i], dp[j] + 1);
    }

    return dp[n - 1];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
  def minCut(self, s: str) -> int:
    n = len(s)
    # isPalindrome[i][j] := True if s[i..j] is a palindrome
    isPalindrome = [[True] * n for _ in range(n)]
    # dp[i] := the minimum cuts needed for a palindrome partitioning of s[0..i]
    dp = [n] * n

    for l in range(2, n + 1):
      i = 0
      for j in range(l - 1, n):
        isPalindrome[i][j] = s[i] == s[j] and isPalindrome[i + 1][j - 1]
        i += 1

    for i in range(n):
      if isPalindrome[0][i]:
        dp[i] = 0
        continue

      # Try all the possible partitions.
      for j in range(i):
        if isPalindrome[j + 1][i]:
          dp[i] = min(dp[i], dp[j] + 1)

    return dp[-1]