132. Palindrome Partitioning II LeetCode Solution

In this guide, you will get 132. Palindrome Partitioning II LeetCode Solution with the best time and space complexity. The solution to Palindrome Partitioning II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Palindrome Partitioning II solution in C++
Palindrome Partitioning II solution in Java
Palindrome Partitioning II solution in Python
Additional Resources

132. Palindrome Partitioning II LeetCode Solution image

Problem Statement of Palindrome Partitioning II

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.

Complexity Analysis

Time Complexity: O(mn)
Space Complexity: O(mn)

132. Palindrome Partitioning II LeetCode Solution in C++

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();
  }
};
/* code provided by PROGIEZ */

132. 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] := 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];
  }
}
// code provided by PROGIEZ

132. Palindrome Partitioning II LeetCode Solution in Python

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]
 # code by PROGIEZ