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.

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.