本文共 1151 字，大约阅读时间需要 3 分钟。

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”,

[

[“aa”,”b”],

[“a”,”a”,”b”]

]

思路：此题第一思路就是回溯，然后就是回溯算法的固定思路解此类问题了。

bool isSubPailndrome(string& str, int low, int high){    if (low == high)return true;    while (low <= high){        if (str[low] == str[high])low++, high--;        else return false;    }    return true;}void dfs_partition(string& s, int start, int end, vector
   
    & path, vector
    
     
      >& res){    if (end == s.size()){        if (isSubPailndrome(s, start,end - 1)){            path.push_back(s.substr(start, end - start));            res.push_back(path);            path.pop_back();        }        return;    }    if (isSubPailndrome(s,start,end - 1)){        path.push_back(s.substr(start, end - start));        dfs_partition(s, end, end + 1, path, res);        path.pop_back();    }    dfs_partition(s, start, end + 1, path, res);}vector
      
       
        > partition(string s) {    vector
        
         
          > res; if (s == "")return res; vector
          
            path; dfs_partition(s, 0, 1, path, res); return res;}
          
         
        
       
      
     
    
   

转载地址：http://esxei.baihongyu.com/