给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。 返回 s 所有可能的分割方案。 示例: 输入: “aab” 输出: [ [“aa”,“b”], [“a”,“a”,“b”] ]
思路：回溯算法，采用递归实现
c++版本 class Solution { public: vector<vector<string>>result; vector<string>temp; bool isPalindrome(string s){ int i=0; int j=s.size()-1; while(i<j){ if(s[i]!=s[j]){ return false; } i++; j--; } return true; } void cursion(string s,int a, int b){ if(a>b){ result.push_back(temp); return; } for(int index=1;index<=b-a+1;index++){ if(isPalindrome(s.substr(a,index))){ temp.push_back(s.substr(a,index)); cursion(s,a+index,b); temp.pop_back(); } } } vector<vector<string>>partition(string s){ cursion(s,0,s.size()-1); return result; } }; python版本 class Solution: def partition(self, s: str) -> List[List[str]]: if not s:return [[]] res=[] for i in range(1,len(s)+1): if s[:i]==s[:i][::-1]: for j in (self.partition(s[i:])): res.append([s[:i]]+j) return res