Share my c++ DP solution 8ms


  • 0
    W

    Enlightened by Python DP solution(https://leetcode.com/discuss/68430/python-dp-solution).
    Required less space.

    class Solution {
    public:
        vector<string> removeInvalidParentheses(string s) {
            int len = s.size();
            vector<vector<int> > dp(len, vector<int>(len, -1)); 
            // dp[i][j] represent the minimum number of removals for s[0:i] followed with j's ")"
            minRemoval(s, s.size() - 1, 0, dp);
            unordered_set<string> ret;
            string cur;
            dfs(s, s.size() - 1, 0, dp, cur, ret);
            return vector<string>(ret.begin(), ret.end());
        }
        
        int minRemoval(string &s, int startIdx, int closedCnt, vector<vector<int> >& dp){
            if(closedCnt < 0)
                return startIdx + 2;
            if(startIdx == -1)
                return closedCnt;
            if(dp[startIdx][closedCnt] != -1)
                return dp[startIdx][closedCnt];
            if(s[startIdx] != '(' && s[startIdx] != ')'){
                return dp[startIdx][closedCnt] = minRemoval(s, startIdx - 1, closedCnt, dp);    
            }
            
            // select the current "(" or ")"
            int dc0;
            int dc1;
            
            // first case: remove
            dc0 = 1 + minRemoval(s, startIdx - 1, closedCnt, dp);
            // second case:
            if(s[startIdx] == '('){
                dc1 = minRemoval(s, startIdx - 1, closedCnt - 1, dp);
            }else if(s[startIdx] == ')'){
                dc1 = minRemoval(s, startIdx - 1, closedCnt + 1, dp);
            }
            dp[startIdx][closedCnt] = min(dc0, dc1);
            return dp[startIdx][closedCnt];
        }
        
        
        void dfs(string &s, int i, int j, vector<vector<int> >& dp, string& cur, unordered_set<string>& ret){
            if(i == -1){
                if(j == 0){
                    string tmp(cur);
                    reverse(tmp.begin(), tmp.end());
                    ret.insert(tmp);
                }
                return;
            }
    
            if(s[i] != '(' && s[i] != ')'){
                cur.push_back(s[i]);
                dfs(s, i - 1, j, dp, cur, ret);
                cur.pop_back();
            }
    
            if(s[i] == '('){
               // if deleted
               if(minRemoval(s, i, j, dp) == 1 + minRemoval(s, i - 1, j, dp)){
                    dfs(s, i - 1, j, dp, cur, ret);
               }
               // not deleted
               if(minRemoval(s, i, j, dp)== minRemoval(s, i - 1, j - 1, dp)){
                    cur.push_back(s[i]);
                    dfs(s, i - 1, j - 1, dp, cur, ret);
                    cur.pop_back();
               }
            }
    
            if(s[i] == ')'){
                // if deleted
                if(minRemoval(s, i, j, dp) == 1 + minRemoval(s, i - 1, j, dp)){
                    dfs(s, i - 1, j, dp, cur, ret);
                }
                // not deleted
                if(minRemoval(s, i, j, dp) == minRemoval(s, i - 1, j + 1, dp)){
                    cur.push_back(s[i]);
                    dfs(s, i - 1, j + 1, dp, cur, ret);
                    cur.pop_back();
                }
            }
        }
    };

Log in to reply
 

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