LeetCode 热题 100_分割回文串（61_131_中等_C++）（递归（回溯））(回溯问题使用类成员变量还是函数传参)

题目描述：

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

输入输出样例：

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

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

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

题解：

解题思路：

思路一（递归（回溯））：

1、题目要求将 s 分割成一些子串，使每个子串都是 回文串。所以就转换为了如何切割 s ，并判断切割的每个字串。
示例1中 ：s = “aab”，其可切割的地方为 ”a|a|b|“，| 为可以切割的位置。 “|aab” 此种切割方式是不可以的，因 ”“ 不为回文串。 “aab|” 的切割方式是可以的。
我们选取 ”a|a|b|“ 中 | 的各种组合，形成不同的切割方式，递归树如下图所示。

2、复杂度分析：
① 时间复杂度：O(n⋅2 ⁿ)，其中n是字符串s的长度。在最坏情况下，s包含n个完全相同的字符，因此它的任意一种划分方法都满足要求。
② 空间复杂度：O(n)，这里不计算返回答案占用的空间。主要取决于path的大小 O(n) 和递归的深度O(n)。

代码实现

代码实现（思路一（递归（回溯）））：

class Solution {
private:
    vector<vector<string>> ans; // 存储所有回文分割结果
    vector<string> path;        // 存储当前正在构建的分割方案

    // 回溯函数，用于探索所有可能的回文分割
    void backtracking(const string& s, int startIndex) {
        // 如果起始位置已经大于或等于字符串的长度，说明已经找到了一组有效的分割方案
        if (startIndex >= s.size()) {
            ans.emplace_back(path); // 将当前的分割方案添加到结果集
            return;
        }

        // 尝试所有从startIndex开始的子串(i看成"|"的位置)
        for (int i = startIndex; i < s.size(); i++) {
            // 判断子串s[startIndex...i]是否是回文
            if (isPalindrome(s, startIndex, i)) {
                // 如果是回文，将该子串添加到当前路径
                path.emplace_back(s.substr(startIndex, i - startIndex + 1));
                
                // 继续回溯，探索下一个可能的回文子串
                backtracking(s, i + 1); // 从i + 1位置开始寻找下一个子串
                
                // 回溯：弹出当前已添加的子串，继续尝试其他可能的分割
                path.pop_back();
            }
        }
    }

    // 辅助函数，判断子串s[left...right]是否是回文
    bool isPalindrome(const string& s, int left, int right) {
        // 从两端向中间检查字符是否相同
        while (left < right) {
            if (s[left++] != s[right--]) return false; // 如果不相同，返回false
        }
        return true; // 如果没有不相同的字符，说明是回文
    }

public:
    // 主函数，将字符串s分割成所有可能的回文子串组合
    vector<vector<string>> partition(string s) {
        ans.clear();  // 清空之前的结果
        path.clear(); // 清空当前的路径（从头开始）

        backtracking(s, 0); // 从索引0开始进行回溯

        return ans; // 返回包含所有回文分割的结果
    }
};

以思路一为例进行调试

#include<iostream>
#include <vector>
using namespace std;


class Solution {
private:
    vector<vector<string>> ans; // 存储所有回文分割结果
    vector<string> path;        // 存储当前正在构建的分割方案

    // 回溯函数，用于探索所有可能的回文分割
    void backtracking(const string& s, int startIndex) {
        // 如果起始位置已经大于或等于字符串的长度，说明已经找到了一组有效的分割方案
        if (startIndex >= s.size()) {
            ans.emplace_back(path); // 将当前的分割方案添加到结果集
            return;
        }

        // 尝试所有从startIndex开始的子串
        for (int i = startIndex; i < s.size(); i++) {
            // 判断子串s[startIndex...i]是否是回文
            if (isPalindrome(s, startIndex, i)) {
                // 如果是回文，将该子串添加到当前路径
                path.emplace_back(s.substr(startIndex, i - startIndex + 1));
                
                // 继续回溯，探索下一个可能的回文子串
                backtracking(s, i + 1); // 从i + 1位置开始寻找下一个子串
                
                // 回溯：弹出当前已添加的子串，继续尝试其他可能的分割
                path.pop_back();
            }
        }
    }

    // 辅助函数，判断子串s[left...right]是否是回文
    bool isPalindrome(const string& s, int left, int right) {
        // 从两端向中间检查字符是否相同
        while (left < right) {
            if (s[left++] != s[right--]) return false; // 如果不相同，返回false
        }
        return true; // 如果没有不相同的字符，说明是回文
    }

public:
    // 主函数，将字符串s分割成所有可能的回文子串组合
    vector<vector<string>> partition(string s) {
        ans.clear();  // 清空之前的结果
        path.clear(); // 清空当前的路径（从头开始）

        backtracking(s, 0); // 从索引0开始进行回溯

        return ans; // 返回包含所有回文分割的结果
    }
};
    

int main(int argc, char const *argv[])
{
    // 定义一个字符串 "aab"
    string str = "aab";
    
    // 创建Solution类的对象s
    Solution s;
    
    // 调用partition方法，传入字符串str，获取所有的回文分割方案
    vector<vector<string>> ans = s.partition(str);
    
    // 遍历回文分割结果ans
    for (int i = 0; i < ans.size(); i++)
    {
        // 输出每个回文分割的开始 "["
        cout << "[";
        
        // 遍历当前回文分割方案中的每个回文子串
        for (int j = 0; j < ans[i].size(); j++)
        {
            // 输出当前的回文子串
            cout << ans[i][j];
            
            // 如果不是当前回文分割方案中的最后一个子串，输出逗号 ","
            if (j != ans[i].size() - 1)
            {
                cout << ",";
            }
        }
        
        // 输出每个回文分割的结束 "]"
        cout << "]";
    }
    
    return 0;  // 程序结束
}

部分代码解读

回溯问题使用类成员变量还是函数传参
对于这个特定的回溯问题，使用类成员变量（全局变量）是更常见的选择，因为：
回溯过程中，result 和 path 是不断变化并传递的状态，作为类的成员变量可以方便地共享这些状态。
isPalindrome 在回溯过程中是一个固定的数据结构，可以在computePalindrome 中事先计算好并作为成员变量保存，避免重复计算。
但如果你考虑代码的灵活性和将来可能的重构（比如支持多线程或处理多个字符串），将这些变量作为函数参数传递可能会更清晰和模块化。
因此，在你当前的实现中，保留它们作为类的成员变量是一个合理的选择。如果你希望代码更加灵活、可重用，可以考虑将它们作为参数传递给函数。

LeetCode 热题 100_分割回文串（61_131)原题链接
欢迎大家和我沟通交流(✿◠‿◠)