leetcode131：分割回文串

题目链接

leetcode

题目描述

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

C++ 代码

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

/* 
    回溯法，枚举所有方案。
    
    对字符串从前向后搜索，搜索时维护如下几个状态：
    1.已经划分好的区间
    2.当前在枚举的区间
    3.枚举字符串 s 的下标
    4.字符串 s

    时间复杂度：O(2^n*n)
        在相邻字符之间放板子，每种放板子的方法对应一种划分方案，
        每个字符间隔有放和不放两种选择，共有 2^(n−1) 个方案。
        对于每个方案，记录方案需要 O(n)。
        所以，时间复杂度是 O(2^n*n)。
    空间复杂度：O(n^2)
        这里不计算返回答案占用的空间。
        递归栈：递归的最大深度为字符串的长度 n，空间复杂度为 O(n)。
        路径存储：当前路径的 path 最多包含 n 个子串，每个子串的长度最多为 n，空间复杂度为 O(n^2)。
*/
class Solution_0 {
public:
    vector<vector<string>> partition(string s) {
        result.clear();
        path.clear();
        if (s.empty()) {
            return {};
        }

        backtrack(s, 0);

        return result;
    }

    void backtrack(const string& s, int start) {
        // 结束条件：起始位置大于 s 的大小
        if (start >= s.size()) {
            result.push_back(path);
            return;
        }

        for (int i = start; i < s.size(); i++) {
            // 剪枝条件：不是回文子串，直接跳过
            if (!isPalindrome(s, start, i)) {
                continue;
            }

            // 获取子串 s[start,i]
            string str = s.substr(start, i-start+1);
            // 选择（添加子串）
            path.push_back(str);
            // 寻找i+1为起始位置的子串
            backtrack(s, i+1);
            // 回溯（弹出本次已经添加的子串）
            path.pop_back();
        }
    }

    bool isPalindrome(const string& s, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            if (s[i] != s[j]) {
                return false;
            }
        }
        return true;
    }

private:
    vector<vector<string>> result;
    vector<string> path;
};

/*
    回溯法 + 记忆化搜索

    时间复杂度：O(2^n*n)
    空间复杂度：O(n^2)
*/
class Solution {
    public:
    vector<vector<string>> partition(string s) {
        result.clear();
        path.clear();
        if (s.empty()) {
            return {};
        }

        // isPalindrome[i][j] 表示 s[i:j] 是否是回文串
        isPalindrome.resize(s.size(), vector<bool>(s.size(), false));
        // 倒序计算：保证在第 i 行时，第 i+1 行已算完
        for (int i = s.size()-1; i >= 0; i--) {
            for (int j = i; j < s.size(); j++) {
                if (j == i) {
                    isPalindrome[i][j] = true;
                } else if (j-i == 1) {
                    isPalindrome[i][j] = (s[i] == s[j]);
                } else {
                    isPalindrome[i][j] = (s[i] == s[j] && isPalindrome[i+1][j-1]);
                }
            }
        }

        backtrack(s, 0);

        return result;
    }

    void backtrack(const string& s, int start) {
        // 结束条件：起始位置大于 s 的大小，说明已经找到了一组分割方案
        if (start >= s.size()) {
            result.push_back(path);
            return;
        }

        for (int i = start; i < s.size(); i++) {
            // 剪枝条件：不是回文子串，直接跳过
            if (!isPalindrome[start][i]) {
                continue;
            }

            // 获取子串 s[start,i]
            string str = s.substr(start, i-start+1);
            // 选择，添加子串
            path.push_back(str);
            backtrack(s, i+1); // 寻找i+1为起始位置的子串
            // 回溯，弹出本次已经添加的子串
            path.pop_back();
        }
    }

private:
    vector<vector<string>> result;
    vector<string> path;
    vector<vector<bool>> isPalindrome;
};

// 辅助函数：打印二维数组
void printArray(const vector<vector<string>>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << "[";
        for (size_t j = 0; j < nums[i].size(); j++) {
            cout << "\"" <<nums[i][j] << "\"";
            if (j != nums[i].size() - 1) cout << ",";
        }
        cout << "]";
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

int main() {
    Solution solution;
    vector<string> s_cases = {
        "aab",
        "a"
    };

    for (size_t i = 0; i < s_cases.size(); i++) {
        string s = s_cases[i];
        cout << "Input: s = \"" << s << "\"" << endl;

        vector<vector<string>> result = solution.partition(s);
        cout << "Output: ";
        printArray(result);
    }

    return 0;
}