题目：

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example

Given s = "aab", return:

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

题解：

Solution 1 ()

class Solution {public:    vector
     
      
       > partition(string s) {        if (s.empty()) {            return {
    {}};        }        vector
       
        
          > res;        vector
         
           v;        dfs(res, v, s, 0);                return res;    }    void dfs(vector
          
           
             > &res, vector
            
              &v, string s, int pos) { if (pos >= s.size()) { res.push_back(v); return; } string str; for (int i = pos; i < s.size(); ++i) { str += s[i]; if (isValid(str)) { v.push_back(str); dfs(res, v, s, i + 1); v.pop_back(); } } } bool isValid(string str) { if (str.empty()) { return true; } int begin = 0; int end = str.size() - 1; for (; begin <= end; ++begin, --end) { if (str[begin] != str[end]) { return false; } } return true; }};
            
           
          
         
        
       
      
     

Solution 1.2 ()

class Solution {public:    bool isPalindrome(string &s, int i, int j){        while(i < j && s[i] == s[j]){            i++;            j--;        }        if(i >= j) {            return true;        } else {            return false;        }    }    void helper(vector
     
      
       > & res, vector
       
         &cur, string &s, int pos){        if(pos == s.size()){            res.push_back(cur);            return;        }        for(int i = pos; i <= s.size() - 1; i++){            if(isPalindrome(s, pos, i)){                cur.push_back(s.substr(pos, i - pos + 1));                helper(res, cur, s, i+1);                cur.pop_back();            }        }    }    vector
        
         
          > partition(string s) {        vector
          
           
            > res; vector
            
              cur; helper(res, cur, s, 0); return res; }};