C++ DP + backtracking solution


  • 0
    J
    class Solution {
    public:
        void helper(string &s, int start, vector<vector<bool>> &isPal, vector<string> &vcur, vector<vector<string>> &res) {
            if(start == s.size()) {
                res.push_back(vcur);
                return;
            }
            for(int i = start; i < s.size(); i++) {
                if(!isPal[start][i]) continue;
                vcur.push_back(s.substr(start, i-start+1));
                helper(s, i+1, isPal, vcur, res);
                vcur.pop_back();
            }
        }
        vector<vector<string>> partition(string s) {
            vector<vector<string>> res;
            if(s.size() == 0) return res;
            //solution to problem 5, decide if substring is palindrome or not first
            vector<vector<bool>> isPal(s.size(), vector<bool>(s.size(), false));
            for(int i = s.size()-1; i >= 0; i--) {
                isPal[i][i] = true;
                for(int j = i+1; j < s.size(); j++) {
                    if(j == i+1) {
                        if(s[i] == s[j])
                            isPal[i][j] = true;
                    }
                    else if(isPal[i+1][j-1] && s[i] == s[j])
                        isPal[i][j] = true;
                }
            }
            vector<string> vcur;
            helper(s, 0, isPal, vcur, res);
            return res;
        }
    };
    

Log in to reply
 

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