分割回文串（回溯算法）

本文参考代码随想录

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例: 输入: “aab” 输出: [ [“aa”,“b”], [“a”,“a”,“b”] ]

思路

切割字符串问题也可以转换成回溯算法：即切割后再在子串上切割

判断回文字符串：双指针法
一个指针从前向后，一个指针从后向前，如果前后指针所指向的元素是相等的，就是回文字符串

class Solution {
private:vector<vector<string>> result;vector<string> path;bool isPalindrome(string s, int start, int end){for(int i = start, j = end; i <= j; i++, j--){if(s[i] != s[j]) return false;}return true;}void backtracking(string s, int startIndex){if(startIndex >= s.size()){result.push_back(path);return;}for(int i = startIndex; i < s.size(); i++){if(isPalindrome(s, startIndex, i)){string ss = s.substr(startIndex, i - startIndex + 1);path.push_back(ss);backtracking(s, i + 1);path.pop_back();}else{continue; //不是回文}}} 
public:vector<vector<string>> partition(string s) {path.clear();result.clear();backtracking(s, 0);return result;}
};