Palindrome Partitioning II Leetcode Solution

In this post, we are going to solve the Palindrome Partitioning II Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

Table of Contents

Problem

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Example 1:

Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

Example 2:

Input: s = "a"
Output: 0

Example 3:

Input: s = "ab"
Output: 1

Constraints:

1 <= s.length <= 2000
s consists of lowercase English letters only.

Now, let’s see the leetcode solution of Palindrome Partitioning II Leetcode Solution.

Palindrome Partitioning II Leetcode Solution in Python

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

    for i in range(n):
      mini = i
      for j in range(i + 1):
        if s[j] == s[i] and (j + 1 > i - 1 or dp[j + 1][i - 1]):
          dp[j][i] = True
          mini = 0 if j == 0 else min(mini, cut[j - 1] + 1)
      cut[i] = mini

    return cut[n - 1]

Palindrome Partitioning II Leetcode Solution in CPP

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] := min 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 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();
  }
};

Palindrome Partitioning II Leetcode Solution in Java

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] := min 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 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];
  }
}

Note: This problem Palindrome Partitioning II is generated by Leetcode but the solution is provided by Chase2learn This tutorial is only for Educational and Learning purpose.