leetcode131 分割回文串

题目

分割回文串

分析

简单dfs问题，关键点在于如何快速的判断回文串。这里我们就可以预先找出所有的回文串，再每次判断的时候只需要读取记录就可以了。

代码

class Solution {
private:
    vector<vector<int>> dp;
    vector<vector<string>> res;

    void dfs(string cur, int start, string s, vector<string>& vec) {

        if (start == s.size()) {
            res.push_back(vec);
            return;
        }

        for (int i = start; i < s.size(); i++) {
            cur += s[i];
            if (dp[start][i]) { //如果这一段是回文串，则装进vec，开始找下一个回文串。
                vec.push_back(cur);
                dfs("", i + 1, s, vec);
                vec.pop_back();
            }
        }
    }
public:
    vector<vector<string>> partition(string s) {
        if (s.empty()) {
            return {};
        }

        dp = vector<vector<int>>(s.size(), vector<int>(s.size(), 0));

        //预先找出所有的回文串，时间复杂度O(n * n)
        for (int l = 1; l <= s.size(); l++) {
            for (int i = 0; i + l - 1 < s.size(); i++) {
                int j = i + l - 1;
                if (s[i] == s[j] && (l <= 2 || dp[i + 1][j - 1] == 1)) {
                    dp[i][j] = 1;
                }
            }
        }

        vector<string> vec;
        dfs("", 0, s, vec);

        return res;
    }
};