92 ms c++ DP solution. Please suggest me where i can improve


  • 0
    M

    My Approach:

    Create a bool 2D vector to capture the palindrome at index i with a length len.
    I start doing this from the rear end of the string. When calculating, I update minCuts required at each index
    Case I: As and when i can reach end from this index directly when forming a palindrome
    Case II: I form a palindrome from curr index and reach another index and use its minCut value to get the minCut value of current index. Update this value across all possible palindromes from curr index.

    class Solution {
    public:
        int minCut(string s) {
        	int n = s.size();
            vector<vector<bool> > bpal(n+1, vector<bool>(n+1,0));
            vector<int> minCut(n,INT_MAX);
            minCut[n-1] = 0;
            for(int i=n-2;i>=0;i--)
            {
            	for(int len=1;len<n+1-i;len++)
            	{
            		if(s[i] ==s[i+len-1] and (len<=2 or bpal[i+1][len-2]))
            		{
            			bpal[i][len] = true;
            			if(i+len==n)
            				minCut[i] = 0;
            			else if(i+len<n and minCut[i+len] !=INT_MAX)
            				minCut[i] = min(minCut[i+len]+1, minCut[i]);
            		}
            	}
            }
            return minCut[0];
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.