131.palindrome-partitioning 分割回文串

问题描述

131.分割回文串

解题思路

利用动态规划来判断字符串是否是回文串:
- if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1];

这里遍历的时候要注意i的遍历顺序;

最后考虑利用回溯法，更新答案。

代码

class Solution {
public:
    vector<vector<string>> res;
    vector<string> res_tmp;

    void track_back(string &s, int index, vector<vector<bool>> &dp) {
        if (index >= s.size()) {
            res.push_back(res_tmp);
            return;
        }
        for (int i = index; i < s.size(); i++) {
            if (dp[index][i]) {
                res_tmp.push_back(s.substr(index, i - index + 1));
                track_back(s, i + 1, dp);
                res_tmp.pop_back();
            }
        }
        return;
    }
    vector<vector<string>> partition(string s) {
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
        for (int i = 0; i < s.size(); i++) {
            dp[i][i] = true;
            if (i < s.size() - 1) {
                if (s[i] == s[i + 1])
                    dp[i][i + 1] = true;
            }
        }
        for (int i = s.size(); i >= 0; i--) {
            for (int j = i + 2; j < s.size(); j++) {
                if (s[i] == s[j])
                    dp[i][j] = dp[i + 1][j - 1];
            }
        }
        track_back(s, 0, dp);
        return res;
    }
};