【LeetCode热题100】131. 分割回文串（回溯）

一.题目要求

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

二.题目难度

中等

三.输入样例

示例 1：
输入：s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]

示例 2：
输入：s = “a”
输出：[[“a”]]

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

四.解题思路

解法1：输入视角，每次切割或者不切割

解法2：答案视角，枚举所有可能子串

五.代码实现

解1

class Solution {
public:
    bool isHui(const string& str) {
        for (int i = 0, j = str.size() - 1; i < j; i++, j--) {
            if (str[i] != str[j])
                return false;
        }
        return true;
    }

    vector<vector<string>> partition(string s) {
        vector<vector<string>> ans;
        vector<string> path;
        dfs(ans, path, s, 1);
        return ans;
    }
    /*
    cutIndex为当前待处理元素进行切割的位置
    从待处理串第一个字母末尾开始走,每次都选择是切割还是不切割
        如果切割，先判断切下来的子串是否是回文串，若是，进行递归
        如果不切割，令cutIndex后移一位
    直到待处理string为空且每次切下来的子串都是回文串 则加入答案
    */
    void dfs(vector<vector<string>>& ans, vector<string>& path, string& s, int cutIndex) {
        if (s == "") {
            ans.push_back(path);
            return;
        }
        if (cutIndex > s.size()) {
            return;
        }
        // 在该位置做切割
        string str = s.substr(0, cutIndex);
        
        //如果是回文串就递归处理剩下的串
        if (isHui(str)) {
            string _s = s.substr(cutIndex);
            path.push_back(str);
            dfs(ans, path, _s, 1);
            path.pop_back();
        }
        // 在该位置不做切割
        dfs(ans, path, s, cutIndex + 1);
    }
};

解2

class Solution {
public:
    bool isHui(const string& str) {
        for (int i = 0, j = str.size() - 1; i < j; ++i, --j) {
            if (str[i] != str[j])
                return false;
        }
        return true;
    }

    vector<vector<string>> partition(string s) {
        vector<vector<string>> ans;
        vector<string> path;
        dfs(ans, path, s, 0); // 从字符串的开始位置开始深度优先搜索
        return ans;
    }

    void dfs(vector<vector<string>>& ans, vector<string>& path, const string& s,
             int start) {
        if (start ==
            s.size()) { // 如果已经遍历到字符串末尾，则将当前路径加入答案
            ans.push_back(path);
            return;
        }
        for (int i = start; i < s.size(); ++i) {
            string str = s.substr(start, i - start + 1);
            if (isHui(str)) { // 只有当当前字符串是回文时，才继续递归
                path.push_back(str);
                dfs(ans, path, s, i + 1); // 从下一个字符开始继续递归搜索
                path.pop_back();          // 回溯
            }
        }
    }
};

六.题目总结

–