palindrome partitioning II -- Leetcode

Question:

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.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

Answer:

1. Recursion method: For large set, time limit exceeded.

class Solution {

public:

    int minCut(string s) {

        vector<string> result=minpalindromepartiton(s);

        return result.size();

    }

    

    vector<string> minpalindromepartiton(string s){

    vector<string> res;

    vector<string> vs;

     if(s.length()==0){

         return res;

     }

     if(s.length()==1){

         res.push_back(s);

         return res;

     }

     

     int count=INT_MAX;

     int k=1;

     

     for(int i=1;i<=s.length();++i){            

        if(ispalindrome(s.substr(0,i))){

            vs=minpalindromepartiton(s.substr(i,s.length()-i));

            

            if(vs.size()<count){

                count=vs.size();

                k=i;

            }

        }            

    }

    if(count==0){

        res.push_back(s);

    }

    else{

        vs=minpalindromepartiton(s.substr(k,s.length()-k));

        vs.insert(vs.begin(),s.substr(0,k));

        res=vs;

    }        

    return res;      

    }

    

    bool ispalindrome(string s){

       for(int i=0;i<s.length();++i){

        if(i<=s.length()/2){

          if(s[i]!=s[s.length()-i-1])

          return false;

        }

        else break;

       }

       return true;

    } 

};

2.DP method: Optimal time solution.

 class Solution{
public:
int minCut(string s) {
     
       int leng = s.size();

        int dp[leng+1];
        bool palin[leng][leng];

      for(int i = 0; i <= leng; i++)
        dp[i] = leng-i;
        for(int i = 0; i < leng; i++)
            for(int j = 0; j < leng; j++)
                palin[i][j] = false;

      for(int i = leng-1; i >= 0; i--){
        for(int j = i; j < leng; j++){
          if(s[i] == s[j] && (j-i<2 || palin[i+1][j-1])){
            palin[i][j] = true;
            dp[i] = min(dp[i],dp[j+1]+1);
          }
        }
      }
      return dp[0]-1;
    }
};