DFS + dp solution


  • 0
    S

    Idea is to use DP to avoid checking palindromes redundantly. Consider substring [i, j] - if we know that substring [i+1,j-1] is a palindrome and S[i] == S[j] then we know for sure [i,j] is also a palindrome. For the rest we just use conventional backtracking DFS approach to trace the paths.

    class Solution {
    public:
        vector<vector<string>> partition(string s) {
            vector<string> path;
            vector<vector<string>> res;
            populate_dp(s);
            dfs(s, 0, s.size(), path, res);
            return res;
        }
        
        void dfs(string &s, int i, int j, vector<string> &p, vector<vector<string>> &r) {
            if (i == j) {
                r.push_back(p);
                return;
            }
            
            for (int k=i; k < j; ++k) {
                if (dp[i][k]) {
                    p.push_back(s.substr(i, k-i+1));
                    dfs(s, k+1, j, p, r);
                    p.pop_back();
                }
            }
            
        }
        
        void populate_dp(string &s) {
            dp.resize(s.size());
            for (auto &v: dp) v.resize(s.size());
            
            for (int i=0;i < s.size(); ++i) dp[i][i] = 1;
            for (int i=1; i < s.size(); ++i) dp[i-1][i] = (s[i-1] == s[i]);
            
            for (int sz=3; sz <= s.size(); ++sz) {
                for (int i=0; i <= s.size()-sz; ++i) {
                    int j=i+sz-1;
                    dp[i][j] = (s[i] == s[j]) && (dp[i+1][j-1]==1);
                }
            }
        }
        
        vector<vector<uint8_t>> dp;
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.