题解 | #所有的回文子串I#

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

本题考察回溯法（Backtracking）算法，需要逐步构建回文串。

题目解答方法的文字分析

我们可以使用回溯法来解决这个问题：

1. 从字符串的第一个字符开始，尝试将其与后续的字符组成回文串。
2. 如果找到了一个回文串，将其加入当前分组，并递归处理剩下的字符。
3. 如果当前分组的所有字符都已经处理完毕，则将当前分组加入结果集。
4. 回溯，将之前加入分组的回文串移出，尝试下一个回文串。
5. 重复上述步骤，直到所有可能的回文串组合都被尝试过。

本题解析所用的编程语言

C++

完整且正确的编程代码

#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    /**
     * 返回所有可能的回文串分组方案，满足每个分组中的牛的名字合在一起都是回文串。
     * 
     * @param s string字符串，表示给定的名字字符串
     * @return string字符串vector<vector<>>，表示所有可能的回文串分组方案
     */
    vector<vector<string>> partition(string s) {
        vector<vector<string>> result; // 存放所有可能的回文串分组方案的结果
        vector<string> current; // 当前分组的回文串
        backtrack(s, 0, current, result); // 使用回溯法逐步构建回文串
        return result; // 返回结果
    }

    /**
     * 回溯法逐步构建回文串，寻找所有可能的回文串分组方案。
     * 
     * @param s string字符串，表示给定的名字字符串
     * @param start int整型，表示当前回溯的起始位置
     * @param current vector<string>&，表示当前的回文串分组
     * @param result vector<vector<string>>&，表示存放所有可能的回文串分组方案的结果
     */
    void backtrack(const string& s, int start, vector<string>& current, vector<vector<string>>& result) {
        if (start == s.size()) { // 如果当前回溯的起始位置等于字符串长度，表示当前分组的所有字符都已处理完毕
            result.push_back(current); // 将当前分组加入结果集
            return;
        }

        // 尝试将起始位置到end位置的子串构成回文串，其中end从start开始递增
        for (int end = start; end < s.size(); end++) {
            if (isPalindrome(s, start, end)) { // 如果子串是回文串
                current.push_back(s.substr(start, end - start + 1)); // 将回文串加入当前分组
                backtrack(s, end + 1, current, result); // 递归处理剩余部分
                current.pop_back(); // 回溯，将之前加入分组的回文串移出
            }
        }
    }

    /**
     * 判断s中起始位置left到right的子串是否为回文串。
     * 
     * @param s string字符串，表示给定的名字字符串
     * @param left int整型，表示子串的起始位置
     * @param right int整型，表示子串的结束位置
     * @return bool，如果子串是回文串返回true，否则返回false
     */
    bool isPalindrome(const string& s, int left, int right) {
        while (left < right) { // 双指针判断子串是否为回文串
            if (s[left] != s[right]) { // 如果左右指针指向的字符不相等，说明子串不是回文串
                return false;
            }
            left++; // 左指针向右移动
            right--; // 右指针向左移动
        }
        return true; // 子串是回文串，返回true
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！