131 分割回文串

https://leetcode.cn/leetbook/read/top-interview-questions-hard/xdoube/

cost:

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> res;
        this->reversableMemo =
            vector<vector<int>>(s.size(), vector<int>(s.size(), -1));
        this->memo = vector<vector<vector<vector<string>>>>(
            s.size(), vector<vector<vector<string>>>(s.size()));
        this->walk(s, 0, s.size() - 1);
        auto& res2 = memo[0][s.size() - 1];
        return res2;
    }

private:
    void walk(string& s, int left, int right) {
        if (!memo[left][right].empty()) {
            return;
        }
        if (left == right) {
            memo[left][right].push_back({s.substr(left, 1)});
            return;
        }
        if (isReversable(s, left, right)) {
            memo[left][right].push_back({s.substr(left, right - left + 1)});
        }
        for (int i = left; i < right; i++) {
            if (isReversable(s, left, i)) {
                this->walk(s, i + 1, right);
                auto ans = memo[i + 1][right];
                if (!ans.empty()) {
                    string&& ss = s.substr(left, i - left + 1);
                    for (auto& vec : ans) {
                        vector<string> vec2 = {ss};
                        vec2.insert(vec2.end(), vec.begin(), vec.end());
                        memo[left][right].push_back(vec2);
                    }
                }
            }
        }
    }
    bool isReversable(string& s, int left, int right) {
        if (reversableMemo[left][right] == 1) {
            return true;
        }
        if (reversableMemo[left][right] == 0) {
            return false;
        }
        while (left < right) {
            if (s[left] != s[right]) {
                reversableMemo[left][right] = 0;
                for (int i = left - 1, j = right + 1; i >= 0 && j < s.size();
                     i--, j++) {
                    reversableMemo[i][j] = 0;
                }
                return false;
            }
            left++;
            right--;
        }

        reversableMemo[left][right] = 1;
        return true;
    }

    vector<vector<vector<vector<string>>>> memo;
    vector<vector<int>> reversableMemo;
};