Leet Code Daily 2024-05-22 - Parlindrome Partitioning

class Solution {
public:
    void dfs(int x, int n, vector<vector<string>>& p, vector<string>& current,
             vector<vector<string>>& ans) {
        if (x == n) {
            ans.push_back(vector<string>(current.begin(), current.end()));
            return;
        }
        for (const auto& t : p[x]) {
            current.push_back(t);
            dfs(x + t.size(), n, p, current, ans);
            current.pop_back();
        }
    }

    vector<vector<string>> partition(string s) {
        const int n = s.size();
        vector<vector<string>> p(n);
        for (int i = 0; i < n; i++) {
            for (int j = i, k = i; j >= 0 && k < n && s[j] == s[k]; j--, k++) {
                p[j].push_back(s.substr(j, k - j + 1));
            }
            if (i + 1 < n) {
                for (int j = i, k = i + 1; j >= 0 && k < n && s[j] == s[k];
                     j--, k++) {
                    p[j].push_back(s.substr(j, k - j + 1));
                }
            }
        }
        vector<string> current;
        vector<vector<string>> ans;
        dfs(0, n, p, current, ans);
        return ans;
    }
};