136-分割回文串
给定一个字符串s,将s分割成一些子串,使每个子串都是回文串。
返回s所有可能的回文串分割方案。样例
给出 s = "aab",返回
[
["aa", "b"],
["a", "a", "b"]
]标签
回溯法 深度优先搜索
思路
使用回溯和递归
code
class Solution {
public:/*** @param s: A string* @return: A list of lists of string*/vector<vector<string>> partition(string s) {// write your code hereint size = s.size();if(size <= 0) {return vector<vector<string> >();}vector<vector<string> > result;vector<string> temp;partition(s, 0, temp, result);return result;}void partition(string s, int current, vector<string> &temp, vector<vector<string> > &result) {if(current == s.size()){result.push_back(temp);return;}for(int i=current; i<s.size(); i++) {if(isPalindrome(s, current, i)) {temp.push_back(s.substr(current,i-current+1));partition(s, i+1, temp, result);temp.pop_back();}}}bool isPalindrome(string s, int begin, int end) {for(int i=begin, j=end; i<j; i++, j--) {if(s[i] != s[j]) {return false;}}return true;}
};