Leetcode Palindrome Partitioning II problem solution

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