fork download

copy

 
 
 
////////////////////// PLEASE PASTE THIS CODE TO LEETCODE PALINDROMIC PARTITION PAGE
 
#define ll long long int
class Solution {
    ll dp[1501][1501];
    ll pal[1501][1501];
 
ll palindrome_partition(string &s,ll i, ll j)
{
	if(dp[i][j]!=-1) return dp[i][j]; // step 3 
 
	if(i>j)
	return dp[i][j]=0;  // it means we no more cuts required. 
 
 
 
	if(pal[i][j]) return dp[i][j]=0;  
 
	ll mina=INT_MAX;
	for(ll k=i;k<=j-1;k++)
	{
        ll left=dp[i][k],right=dp[k+1][j]; ll tempans=0;
        if(left==-1)
		left=palindrome_partition(s,i,k);
        if(right==-1)
		right=palindrome_partition(s,k+1,j);
 
        tempans=left+right+1;
		mina=min(mina,tempans);
	}
 
	return (dp[i][j]=mina);
}
public:
    int minCut(string s) {
        if(s.length()==0) return 0;
        memset(dp,-1,sizeof(dp));
        memset(pal,0,sizeof(pal));
        ll n=s.length();
        for(int i=0;i<n;i++)
		pal[i][i]=1;
 
		// explicitly for 2 length
		for(int i=0;i<n-1;i++)
		{
			if(s[i]==s[i+1])
			pal[i][i+1]=1;
		}
 
		for(int i=2;i<n;i++)
		{
			for(int j=0;j+i<n;j++)
			{
				if(s[j]==s[j+i] and pal[j+1][j+i-1]==1)
				pal[j][j+i]=1;
			}
		}
 
        return palindrome_partition(s,0,n-1);
    }
};

prog.cpp:11:25: error: ‘string’ has not been declared
 ll palindrome_partition(string &s,ll i, ll j)
                         ^~~~~~
prog.cpp:33:16: error: ‘string’ has not been declared
     int minCut(string s) {
                ^~~~~~
prog.cpp: In member function ‘long long int Solution::palindrome_partition(int&, long long int, long long int)’:
prog.cpp:21:10: error: ‘INT_MAX’ was not declared in this scope
  ll mina=INT_MAX;
          ^~~~~~~
prog.cpp:21:10: note: ‘INT_MAX’ is defined in header ‘<climits>’; did you forget to ‘#include <climits>’?
prog.cpp:1:1:
+#include <climits>
 
prog.cpp:21:10:
  ll mina=INT_MAX;
          ^~~~~~~
prog.cpp:27:8: error: ‘min’ was not declared in this scope
   mina=min(mina,tempans);
        ^~~
prog.cpp:27:8: note: suggested alternative: ‘mina’
   mina=min(mina,tempans);
        ^~~
        mina
prog.cpp: In member function ‘int Solution::minCut(int)’:
prog.cpp:34:14: error: request for member ‘length’ in ‘s’, which is of non-class type ‘int’
         if(s.length()==0) return 0;
              ^~~~~~
prog.cpp:35:9: error: ‘memset’ was not declared in this scope
         memset(dp,-1,sizeof(dp));
         ^~~~~~
prog.cpp:35:9: note: ‘memset’ is defined in header ‘<cstring>’; did you forget to ‘#include <cstring>’?
prog.cpp:1:1:
+#include <cstring>
 
prog.cpp:35:9:
         memset(dp,-1,sizeof(dp));
         ^~~~~~
prog.cpp:37:16: error: request for member ‘length’ in ‘s’, which is of non-class type ‘int’
         ll n=s.length();
                ^~~~~~
prog.cpp:44:10: error: invalid types ‘int[int]’ for array subscript
    if(s[i]==s[i+1])
          ^
prog.cpp:44:18: error: invalid types ‘int[int]’ for array subscript
    if(s[i]==s[i+1])
                  ^
prog.cpp:52:11: error: invalid types ‘int[int]’ for array subscript
     if(s[j]==s[j+i] and pal[j+1][j+i-1]==1)
           ^
prog.cpp:52:19: error: invalid types ‘int[int]’ for array subscript
     if(s[j]==s[j+i] and pal[j+1][j+i-1]==1)
                   ^

Standard output is empty