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     bool isPalindrome(string s){ 2         int l = s.length(); 3         if(l == 1) 4             return true; 5         int i = 0; 6         while(i < l/2){ 7             if(s[i] != s[l-i-1]) 8                 return false; 9             i++;10         }11         return true;12     }13     void search(vector
          
           
             > &result, vector
            
              &tmp, string s, int index){14         if(index == s.length()){ 15             result.push_back(tmp);16             return;17         }18         for(int i = index+1; i <= s.length(); i++){19             string t = s.substr(index, i-index);20             if(isPalindrome(t)){21                 tmp.push_back(t);22                 search(result, tmp, s, i);23                 tmp.erase(tmp.end()-1);24             }25         }26     }27     vector
             
              
                > partition(string s) {28         // IMPORTANT: Please reset any member data you declared, as29         // the same Solution instance will be reused for each test case.30         vector
               
                
                  > result;31 vector
                 
                   tmp;32 search(result, tmp, s, 0);33 return result;34 }