LeetCode: Palindrome Partition

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"]  ] 地址： 算法：可以用动态规划来解决。用一个二维数组dp来存储所有子问题的解，一维数组dp[i]用来存储0～i的字串的所有解，其中每个解用最后一个回文开始位置来标记。比如对于上面的字符串“aab”， dp[0]={0},dp[1]={0,1},dp[2]={2}。这样，在构造解的过程中就可以采用递归的方法，对dp[n-1]中的所有值dp[n-1][j]先递归构造出字串0～dp[n-1][j]-1，然后在加上dp[n-1][j]~n-1 字串。具体代码：

1 class Solution { 2 public: 3     vector
        
         
           > partition(string s) { 4         int n = s.size(); 5         if (n < 1)  return vector
          
           
             >(); 6         vector
            
             
               > dp(n); 7 dp[0].push_back(0); 8 for (int i = 1; i < n; ++i){ 9 if(isPalindrome(s.substr(0,i+1))){10 dp[i].push_back(0);11 }12 dp[i].push_back(i);13 for (int j = i-2; j >= 0; --j){14 if(isPalindrome(s.substr(j+1,i-j))){15 dp[i].push_back(j+1);16 }17 }18 }19 return constructResult(s,dp,n);20 }21 bool isPalindrome(const string &s){22 int len = s.size();23 int n = len / 2;24 int i = 0;25 while(i < n && s[i] == s[len-1-i]) ++i;26 return i == n;27 }28 vector
              
               
                 > constructResult(string &s, vector
                
                 
                   > &dp,int n){29 if (n < 1){30 return vector
                  
                   
                     >();31 }32 vector
                    
                     ::iterator it = dp[n-1].begin();33 vector
                     
                      
                        > result;34 for (; it != dp[n-1].end(); ++it){35 if (*it == 0){36 vector
                       
                         temp1;37 temp1.push_back(s.substr(0,n));38 result.push_back(temp1);39 continue;40 }41 vector
                        
                         
                           >temp2 = constructResult(s,dp,*it);42 vector
                          
                           
                             >::iterator str_it = temp2.begin();43 for(; str_it != temp2.end(); ++str_it){44 str_it->push_back(s.substr(*it,n-(*it)));45 result.push_back(*str_it);46 }47 }48 return result;49 }50 };
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        

第二题：

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.

地址：

算法：同样用动态规划来解决，但这次只要用一维数组dp来储存所有子问题。其中dp[i]表示字串0～i所用的最小cut，dp[i+1]=min{dp[j-1] | 0 =< j <= i+1 且 字串j~i+1是回文}。代码：

1 class Solution { 2 public: 3     int minCut(string s) { 4         int n = s.size(); 5         if(n < 1)   return 0; 6         vector
        
          dp(n); 7         dp[0] = 0; 8         for(int i = 1; i < n; ++i){ 9             if(isPalindrome(s.substr(0,i+1))){10                 dp[i] = 0;11                 continue;12             }13             int min_value = n;14             for(int j = i-1; j >= 0; --j){15                 if(dp[j]+1 < min_value){16                     if(isPalindrome(s.substr(j+1,i-j))){17                         min_value = dp[j] + 1;18                     }19                 }20             }21             dp[i] = min_value;22         }23         return dp[n-1];24     }25     bool isPalindrome(const string &s){26         int len = s.size();27         int n = len / 2;28         int i = 0;29         while(i < n && s[i] == s[len-1-i])    ++i;30         return i == n;31     }32 };