131. Palindrome Partitioning

backtracking O(n*2ⁿ) time 即worst case “aaa”
预处理isPalin剪枝提速

class Solution {
public:
    vector<vector<string>> partition(string s) {
        n = s.length();
        isPalin.resize(n, vector<bool>(n));
        computeIsPalin(s);
        dfs(s, 0);
        return res;
    }

    void computeIsPalin(const string &s) {
        for (int i = 0; i < n; ++i) {
            isPalin[i][i] = true;
        }
        for (int i = 0; i < n - 1; ++i) {
            isPalin[i][i + 1] = (s[i] == s[i + 1]);
        }
        for (int len = 2; len <= n; ++len) {
            for (int i = 0, j = i + len; i < n && j < n; ++i, ++j) {
                isPalin[i][j] = isPalin[i + 1][j - 1] && (s[i] == s[j]);
            }
        }
    }

    void dfs(string_view s, int b) {
        if (b == n) {
            vector<string> vs(begin(v), end(v));
            res.push_back(move(vs));
        }
        for (int i = b; i < n; ++i) {
            if (isPalin[b][i]) {
                v.push_back(s.substr(b, i + 1 - b));
                dfs(s, i + 1);
                v.pop_back();
            }
        }
    }

    int n;
    vector<string_view> v;
    vector<vector<string>> res;
    vector<vector<bool>> isPalin;
};

class Solution {
public:
    vector<vector<string>> partition(string s) {
        int n = s.length();
        isPalin.resize(n, vector<bool>(n));
        computeIsPalin(s);
        dfs(s, 0);
        return res;
    }

    void computeIsPalin(const string &s) {
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            isPalin[i][i] = true;
        }
        for (int i = 0; i < n - 1; ++i) {
            isPalin[i][i + 1] = (s[i] == s[i + 1]);
        }
        for (int len = 2; len <= n; ++len) {
            for (int i = 0, j = i + len; i < n && j < n; ++i, ++j) {
                isPalin[i][j] = isPalin[i + 1][j - 1] && (s[i] == s[j]);
            }
        }
    }

    void dfs(const string &s, int b) {
        if (b == s.length()) {
            res.push_back(v);
        }
        for (int i = b; i < s.length(); ++i) {
            if (isPalin[b][i]) {
                v.push_back(s.substr(b, i + 1 - b));
                dfs(s, i + 1);
                v.pop_back();
            }
        }
    }

    vector<string> v;
    vector<vector<string>> res;
    vector<vector<bool>> isPalin;
};

class Solution {
public:
    vector<vector<string>> partition(string s) {
        int n = s.length();
        isPalin = vector<vector<bool>>(n, vector<bool>(n));
        computeIsPalin(s);
        return helper(s, 0, n - 1);
    }

    void computeIsPalin(const string &s) {
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            isPalin[i][i] = true;
        }
        for (int i = 0; i < n - 1; ++i) {
            isPalin[i][i + 1] = (s[i] == s[i + 1]);
        }
        for (int len = 2; len <= n; ++len) {
            for (int i = 0, j = i + len; i < n && j < n; ++i, ++j) {
                isPalin[i][j] = isPalin[i + 1][j - 1] && (s[i] == s[j]);
            }
        }
    }

    vector<vector<string>> helper(const string &s, int l, int r) {
        vector<vector<string>> res;
        for (int i = l; i <= r; ++i) {
            if (isPalin[l][i]) {
                if (i == r) {
                    res.push_back({s.substr(l, i + 1 - l)});
                } else {
                    for (auto &&v : helper(s, i + 1, r)) {
                        res.push_back({s.substr(l, i + 1 - l)});
                        res.back().insert(res.back().end(), v.begin(), v.end());
                    }
                }
            }
        }
        return res;
    }

    vector<vector<bool>> isPalin;
};