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"]  ]    分析：本题可以用两种方法解，一种是DFS搜索所有情况，另一个方式是用动态规划。DFS在搜索的时候会有很多判断某个子字符串是否为palindrome的重叠子问题。 DFS方法代码如下：

class Solution {public:    vector
     
      
       > partition(string s) {        vector
       
        
          > result;        vector
         
           path;                dfs(result, path, s, 0);                return result;    }        void dfs(vector
          
           
             > &result, vector
            
              &path, string s, int start){ if(start == s.length()){ result.push_back(path); return; } for(int i = start; i < s.length(); i++){ string tmp = s.substr(start, i-start+1); if(isPalindrome(tmp)){ path.push_back(tmp); dfs(result, path, s, i+1); path.pop_back(); } } } bool isPalindrome(string s){ int l = 0, r = s.length() - 1; for(; l <= r && s[l] == s[r]; l++, r--); return l > r; }};
            
           
          
         
        
       
      
     

 动态规划算法如下：

class Solution {public:    vector
     
      
       > partition(string s) {        int n = s.length();                vector
       
        
          > f(n, vector
         
          (n, false));                for(int i = 0; i < n; i++)            for(int j = i; j >= 0; j--){                if(i == j || j + 1 < i && f[j+1][i-1] && s[j] == s[i] || j + 1 == i && s[j] == s[i])                    f[j][i] = true;            }                vector
          
           
             > cache[n+1];//cache[0] indicates an empty vector
            
              cache[0].push_back(vector
             
              ()); for(int i = 0; i < n; i++) for(int j = -1; j < i; j++){ if(f[j+1][i]){ for(auto v:cache[j+1]){ v.push_back(s.substr(j+1, i-j)); cache[i+1].push_back(v); } } } return cache[n]; }};