当前位置：首页 > article >正文

分割回文串(DFS)

article 2024/11/8 21:31:34

给你一个字符串 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));  // 加入当前子串到 path
                dfs(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 的子串。