• Time:O(mn)
• Space:O(mn)

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

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];
}
}
``````

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]
``````