131. Palindrome Partitioning

题目链接

https://leetcode.com/problems/palindrome-partitioning/

代码

class Solution {
public:
    void dfs(vector<vector<string>> &ans, vector<string> &vs, string &s, int cnt, int pos, vector<vector<bool>> &tag) {
        int len = s.length();
        if (cnt == 1) {
            if (tag[pos][len - 1]) {
                vs.push_back(s.substr(pos, len - pos));
                ans.push_back(vs);
                vs.pop_back();
            }
            return;
        }

        if (pos >= len) {
            return;
        }

        for (int i = pos; i < len && len - i >= cnt; ++i) {
            if (tag[pos][i]) {
                vs.push_back(s.substr(pos, i - pos + 1));
                dfs(ans, vs, s, cnt - 1, i + 1, tag);
                vs.pop_back();
            }
        }
    }

    vector<vector<string>> partition(string s) {
        int len = s.length();
        //tag[i][j]表示i到j是否是回文
        vector<vector<bool>> tag(len, vector<bool>(len, false));
        for (int i = 0; i < len; ++i) {
            tag[i][i] = true;
        }
        for (int i = 1; i < len; ++i) {
            if (s[i] == s[i - 1]) {
                tag[i - 1][i] = true;
            }
        }
        for (int i = 2; i < len; ++i) {
            for (int p = 0, q = i; q < len; ++q, ++p) {
                if (s[p] == s[q] && tag[p + 1][q - 1]) {
                    tag[p][q] = true;
                }
            }
        }

        vector<vector<string>> ans;
        vector<string> vs;
        //找切分成i个字符串并且符合条件的
        for (int i = 1; i <= len; ++i) {
            dfs(ans, vs, s, i, 0, tag);
        }
        return ans;
    }
};