M131.分割回文串

dp, backtracking, https://leetcode.cn/problems/palindrome-partitioning/

思路：dp预先计算字符串所有子串的回文信息并存储在DP表中，然后通过回溯算法进行深度优先搜索，在每一步利用DP表快速判断子串是否回文来指导分割决策，当搜索到字符串末尾时将当前分割方案加入结果集，用时一个小时（还是不熟练，小错误不断，太菜了）

cpp

class Solution {
public:
    vector<vector<string>> partition(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                if (i == j) {
                    dp[i][j] = true;  
                } else if (j == i + 1) {
                    dp[i][j] = (s[i] == s[j]);  
                } else {
                    dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1]; 
                }
            }
        }

        vector<vector<string>> result;
        vector<string> path;  
        backtrack(s, 0, dp, path, result);
        return result;
    }
    void backtrack(const string& s, int start, const vector<vector<bool>>& dp, 
                   vector<string>& path, vector<vector<string>>& result) {
        if (start == s.size()) {  
            result.push_back(path);
            return;
        }
        for (int end = start; end < s.size(); ++end) {
            if (dp[start][end]) {  
                path.push_back(s.substr(start, end - start + 1));  
                backtrack(s, end + 1, dp, path, result);           
                path.pop_back();  
            }
        }
    }
};

cpp

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

class Solution
{
public:
    vector<vector<string>> partition(string s)
    {
        int n = s.length();
        vector<vector<string>> ans;
        vector<string> a;

        auto dfs = [&](this auto &&dfs, int i)
        {
            if (i == n)
            {
                ans.emplace_back(a);
                return;
            }

            for (int j = i; j < n; ++j)
            {
                string sub = s.substr(i, j - i + 1);
                if (isPanlindromic(sub))
                {
                    a.emplace_back(sub);
                    dfs(j + 1);
                    a.pop_back();
                }
            }
        };

        dfs(0);
        return ans;
    }

private:
    inline bool isPanlindromic(const string &s)
    {
        int l = 0, r = s.length() - 1;
        while (l < r)
            if (s[l++] != s[r--])
                return false;
        return true;
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    Solution sol;
    string s = "aab";
    for (auto i : sol.partition(s))
    {
        for (auto j : i)
            cout << j << ' ';
        cout << '\n';
    }
    return 0;
}

M131.分割回文串 ​

M131.分割回文串