# Share my c++ DP solution 8ms

• 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();
}
}
}
};``````

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