C++ DP + Backtracking


  • 0
    Y

    This dp technique for substring palindrome can be applied to many other scenarios.

    class Solution {
    public:
        vector<vector<string>> partition(string s) {
            vector<vector<string>> res;
            int n = s.size();
            if (n == 0) return res;
            
            vector<vector<bool>> dp(n, vector<bool>(n, false));
            for (int l = 0; l < n; l++) {
                for (int i = 0; i + l < n; i++) {
                    if (l == 0) dp[i][i + l] = true;
                    else if (l == 1) dp[i][i + l] = (s[i] == s[i + l]);
                    else dp[i][i + l] = (s[i] == s[i + l]) && dp[i + 1][i + l - 1];
                }
            }
            
            vector<string> cur;
            backtrack(res, cur, s, 0, dp);
            
            return res;
        }
        
        void backtrack(vector<vector<string>> &res, vector<string> &cur, string &s, int idx, vector<vector<bool>> &dp) {
            if (idx == s.size()) {
                res.push_back(cur);
                return;
            }
            
            for (int j = idx; j < s.size(); j++) {
                if (dp[idx][j]) {
                    cur.push_back(s.substr(idx, j - idx + 1));
                    backtrack(res, cur, s, j + 1, dp);
                    cur.pop_back();
                }
            }
        }
    };
    

Log in to reply
 

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