In this Leetcode Palindrome Partitioning II problem solution, we have 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.
Problem solution in Python.
def f(s,ci,d):
l=len(s)
if ci==l:return 0
if d[ci]!=-1:return d[ci]
a=math.inf
r=rev=''
for i in range(ci,l):
r+=s[i]
rev=s[i]+rev
if r==rev:a=min(1+f(s,i+1,d),a)
d[ci]=a
return a
class Solution:
def minCut(self, s: str) -> int:
return f(s,0,[-1 for i in range(len(s))])-1
Problem solution in Java.
class Solution {
public int minCut(String s) {
int l = s.length();
boolean [][] isPal = new boolean [l][l];
for(int i = l-1; i>= 0; i--)
for(int j = i;j<l;j++)
if(s.charAt(i) == s.charAt(j) && ((j-i) < 2 || isPal[i+1][j-1]))
isPal[i][j] = true;
int [] min = new int [l+1];
for(int i =0;i<l;i++){
min[i+1] = i+1;
for(int j = i;j>=0;j--)
if(isPal[j][i])
min[i+1] = Math.min(min[i+1], 1+min[j]);
}
return min[l]-1;
}
}
Problem solution in C++.
vector<vector<bool>> memo;
vector<int> r;
int dfs(int i,string& s)
{
if(i>=s.length())
return -1;
else if(r[i]!=-1)
return r[i];
else
{
int q=s.length();
for(int j=i;j<s.length();++j)
if(memo[i][j])
q=min(q,1+dfs(j+1,s));
return r[i]=q;
}
}
int minCut(string s)
{
int n=s.size();
memo.resize(n,vector<bool>(n,false));
r.resize(n,-1);
for(int l = 1; l <=n; l++)
for(int i = 0; i < n; i++)
{
int j = i + l - 1;
if(j >= n) break;
memo[i][j] = (i + 1 > j - 1 || memo[i + 1][j - 1]) && s[i] == s[j];
}
return dfs(0,s);
}
Problem solution in C.
#define MAXN 2048
bool dp[MAXN][2]={0};
int cut[MAXN];
int minCut(char* s) {
const int slen = strlen(s);
memset(cut,0x3f,sizeof(int)*slen);
for(int j = 0; j < slen; j++)
for(int i = 0; i <=j; i++)
{
dp[i][j&1] = false;
if(s[i] == s[j] && (i+1 >= j || dp[(i+1)][(j-1)&1]))
{
dp[i][j&1] = true;
int tmp = (i?cut[i-1]:0) + 1;
if(tmp < cut[j])
cut[j] = tmp;
}
}
return cut[slen-1]-1;
}