Palindrome Partitioning

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"]  ]

 

历遍的说……

 

1 class Solution { 2     public: 3         vector
      
       
         > result; 4  5         void search_palin(const string& s, int start, vector
        
          parti, 6                 const vector
         
          
            >& is_palin) 7         { 8             if (start == s.length()) { 9                 result.push_back(parti);10                 return;11             }12             for (int i = start; i < s.length(); ++i) {                              13                 if (is_palin.at(start).at(i)) {14                     parti.push_back(s.substr(start, i - start + 1));                15                     search_palin(s, i + 1, parti, is_palin);                        16                     parti.pop_back();                                               17                 }18             }19         }20         21         vector
           
            
             > partition(string s) { 22 // Start typing your C/C++ solution below 23 // DO NOT write int main() function 24 25 // if char i to char j palin 26 int slen = s.length(); 27 vector
             
              
                > is_palin(slen, vector
               
                (slen, false)); 28 for (int j = 0; j < slen; ++j) { 29 for (int i = 0; i <= j; ++i) { 30 if (i == j) { 31 is_palin.at(i).at(j) = true; 32 } else if (i + 1 == j) { 33 is_palin.at(i).at(j) = s[i] == s[j]; 34 } else {35 is_palin.at(i).at(j) = is_palin.at(i + 1).at(j - 1) && s[i] == s[j];36 }37 }38 }39 40 vector
                
                  parti;41 result.clear();42 parti.clear();43 search_palin(s, 0, parti, is_palin);44 return result;45 }46 };