Problem
Given a string, return the minimum number of cuts to partition it into palindromes.
Example
Input: "aab"
Output: 1
["aa","b"] needs one cut.Solution
DP. cuts[i] = min cuts for s[:i]. Precompute palindrome table to look up s[j..i] in O(1).
def min_cut(s):
n = len(s)
pal = [[False] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
for j in range(i, n):
if s[i] == s[j] and (j - i < 2 or pal[i+1][j-1]):
pal[i][j] = True
cuts = list(range(n))
for i in range(n):
if pal[0][i]: cuts[i] = 0
else:
for j in range(1, i + 1):
if pal[j][i]: cuts[i] = min(cuts[i], cuts[j-1] + 1)
return cuts[n-1]function minCut(s) {
const n = s.length;
const pal = Array.from({length: n}, () => new Array(n).fill(false));
for (let i = n - 1; i >= 0; i--) {
for (let j = i; j < n; j++) {
if (s[i] === s[j] && (j - i < 2 || pal[i+1][j-1])) pal[i][j] = true;
}
}
const cuts = Array.from({length: n}, (_, i) => i);
for (let i = 0; i < n; i++) {
if (pal[0][i]) cuts[i] = 0;
else for (let j = 1; j <= i; j++) {
if (pal[j][i]) cuts[i] = Math.min(cuts[i], cuts[j-1] + 1);
}
}
return cuts[n-1];
}int minCut(string s) {
int n = s.size();
vector<vector<bool>> pal(n, vector<bool>(n, false));
for (int i = n - 1; i >= 0; i--)
for (int j = i; j < n; j++)
if (s[i] == s[j] && (j - i < 2 || pal[i+1][j-1])) pal[i][j] = true;
vector<int> cuts(n);
for (int i = 0; i < n; i++) cuts[i] = i;
for (int i = 0; i < n; i++) {
if (pal[0][i]) cuts[i] = 0;
else for (int j = 1; j <= i; j++)
if (pal[j][i]) cuts[i] = min(cuts[i], cuts[j-1] + 1);
}
return cuts[n-1];
}public int minCut(String s) {
int n = s.length();
boolean[][] pal = new boolean[n][n];
for (int i = n - 1; i >= 0; i--)
for (int j = i; j < n; j++)
if (s.charAt(i) == s.charAt(j) && (j - i < 2 || pal[i+1][j-1])) pal[i][j] = true;
int[] cuts = new int[n];
for (int i = 0; i < n; i++) cuts[i] = i;
for (int i = 0; i < n; i++) {
if (pal[0][i]) cuts[i] = 0;
else for (int j = 1; j <= i; j++)
if (pal[j][i]) cuts[i] = Math.min(cuts[i], cuts[j-1] + 1);
}
return cuts[n-1];
}Complexity
- Time: O(n²)
- Space: O(n²)
Explanation
Two DPs: palindrome lookup table, then min cuts. Without precomputed palindromes, checking each substring would push to O(n³).
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?