分割回文串(DFS)

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串。返回 s 所有可能的分割方案。

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

提示：

• 1 <= s.length <= 16
• s 仅由小写英文字母组成

DFS:

class Solution {vector<string> path;vector<vector<string>> v;
public:vector<vector<string>> partition(string s) {dfs(s, 0);return v;}void dfs(string s, int i){  //i 是一个索引,表示当前递归调用时正在考虑的子串的起始位置if (i == s.size()) { //当 i 达到字符串 s 的末尾时，说明找到了一个完整的回文分割方案v.push_back(path);return;}for(int j = i; j < s.size(); j++){if(is(s, i, j)){   // 如果 s[i:j] 是回文path.push_back(s.substr(i, j - i + 1));  // 加入当前子串到 pathdfs(s, j + 1);   // 递归调用，从下一个索引开始继续分割path.pop_back();  // 回溯，撤销前面的选择}}}bool is(string& s, int left, int right){ //检查字符串 s 的 [left, right] 区间是否是回文。while(left < right){if(s[left++] != s[right--]){return false;}}return true;}
};

vector<string> path：用于存储当前分割方案中的回文子串

vector<vector<string>> v：存储所有符合条件的回文分割方案

dfs 函数在每次递归时，从位置 i 开始，检查从 i 到 j 的每个子串是否是回文。一旦找到一个回文子串，就递归到下一个位置（即从 j + 1 开始），继续对剩余的字符串进行分割，直到整个字符串都被分割成回文子串为止。

path.push_back(s.substr(i, j - i + 1));

这一行代码的作用是将字符串 s 的一个子串添加到 path 中。

substr(i, len)：用于提取从 i 开始，长度为 len 的子串。

• i：子串的起始位置（从 0 开始）。
• len：子串的长度。