palindrome partitioning I,II(C++ code)

LeetCode Palindrome Partitioning, Feb 28,13

Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

void partition(string s, int level, vector<string> &path, vector<vector<string>> &res, bool **A){

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

       res.push_back(path); return;

   }

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

       if(A[level][i]){

          path.push_back(s.substr(level, i-level+1));

          partition(s,i+1,path,res,A);

          path.pop_back(); 

       }

   } 

} 

vector<vector<string>> partition(string s) {
        vector<vector<string>> res;

        vector<string> path;

        bool **A = new bool*[s.length()];

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

           A[i] = new bool[s.length()]; 

           A[i][i] = true; 

           if(i > 0) A[i-1][i] = (s[i] == s[i-1])? true :false;

           for(int j = 0; j < i-1; j++){

             if(!A[j+1][i-1]|| s[i] != s[j]) A[j][i] = false;

             else A[j][i] = true;

           }

        }

        partition(s, 0,path, res,A);

for(int i = 0; i < s.length(); ++i) {
    delete [] A[i];
}
delete [] A; 

      return res;

        
    } 

Palindrome Partitioning II， Mar 12

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.


暴力解法超时了。。
void countcut(string s, bool **A, int level, int &minsofar, int count){
  if(level == s.length()) {
   minsofar = min(minsofar, count-1);
   return;
 }
 for(int i = level; i < s.length(); i++){
  if(A[level][i]) {
      countcut(s,A,i+1,minsofar,count+1);
  }
 }

}
 int minCut(string s) {
       int minsofar = s.length() - 1;
   

        bool **A = new bool*[s.length()];

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

           A[i] = new bool[s.length()]; 

           A[i][i] = true; 

           if(i > 0) A[i-1][i] = (s[i] == s[i-1])? true :false;

           for(int j = 0; j < i-1; j++){

             if(!A[j+1][i-1]|| s[i] != s[j]) A[j][i] = false;

             else A[j][i] = true;

           }

        }

       countcut(s,A,0,minsofar, 0);

for(int i = 0; i < s.length(); ++i) {
    delete [] A[i];
}
delete [] A; 

return minsofar; 

       
    }

换个想法，按切的刀数从小到大考虑，对平均情况会快些， 但考虑到最坏情况跟暴力解法一样，大集合还是超时了。。

---------------

bool countcut(string s, bool **A, int count, int start){

 if(count == 0) return A[start][s.length()-1];

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

   if(A[start][i]) {

        if(countcut(s,A,count-1,i+1)) return true;

   }

 } 

 return false;

}

int minCut(string s) {
       int minsofar = s.length() - 1;

   
bool **A = new bool*[s.length()];  
for(int i = 0; i < s.length(); i++){ 
 A[i] = new bool[s.length()]; A[i][i] = true;  
 if(i > 0) A[i-1][i] = (s[i] == s[i-1])? true :false;  
 for(int j = 0; j < i-1; j++){  
   if(!A[j+1][i-1]|| s[i] != s[j]) A[j][i] = false; 
   else A[j][i] = true; } 
 }

int count;
for( count = 0; count < s.length(); count++){
 if(countcut(s,A,count,0)) break;
}

for(int i = 0; i < s.length(); ++i) { 
 delete [] A[i]; }  
delete [] A;   

return count;
       
    }

----------
正解原来是DP，能用DP一定不要用recursion啊，下面这个来自leetcode ID wangya,自己懒得写了。。

int minCut(string str){

        int leng = str.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(str[i] == str[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;
    }