LeetCode 301. Remove Invalid Parentheses(DP)
- 2020 年 3 月 9 日
- 筆記
DP 险过。
dp[i][j] :means it need remove at least dp[i][j] characters to get vaild parenthese from position i to postion j in string. vector str[i][j] store the parenthese string for example : "()())" dp[0][1]=0 vector[0][1]=["()"] dp[0][2]=1 vector[0][2]=["()"] dp[1][2]=0 vector[1][2]=["()"] dp[0][3]=0 vector[1][2]=["()()"] dp[0][4]=1 vector[0][4]=["()()","(())"]
dp[0][4]=min(dp[0][1]+d[1][4],….dp[0][3]+dp[4][4],dp[1][3])
class Solution { public: vector<string> str[1005][1005]; int dp[1005][1005]; vector<string> removeInvalidParentheses(string s) { if(s=="") { str[0][0].push_back(""); return str[0][0]; } for(int i=0;i<s.length();i++) { if(s[i]=='('||s[i]==')') { dp[i][i] = 1; str[i][i].push_back(""); } else { dp[i][i] = 0; string ss; ss+=s[i]; str[i][i].push_back(ss); } } for(int l=1;l<s.length();l++) { for(int i=0;i+l<s.length();i++) { int j = i+l; dp[i][j]=INT_MAX; for(int k=i;k<j;k++) { if(dp[i][j]>=dp[i][k]+dp[k+1][j]) { dp[i][j]=dp[i][k]+dp[k+1][j]; str[i][j].clear(); for(int p=0;p<str[i][k].size();p++) { for(int q=0;q<str[k+1][j].size();q++) { string ss = str[i][k][p]+str[k+1][j][q]; if(std::find(str[i][j].begin(), str[i][j].end(), ss) == str[i][j].end()) str[i][j].push_back(ss); } } } } if(s[i]=='('&&s[j]==')') { if(l==1) { dp[i][j]=0; str[i][j].clear(); str[i][j].push_back("()"); } else { if(dp[i][j]>=dp[i+1][j-1]) { if(dp[i][j]>dp[i+1][j-1]) str[i][j].clear(); dp[i][j]=dp[i+1][j-1]; for(int p=0;p<str[i+1][j-1].size();p++) { string ss = s[i]+str[i+1][j-1][p]+s[j]; if(std::find(str[i][j].begin(), str[i][j].end(), ss) == str[i][j].end()) str[i][j].push_back(ss); } } } } else { if(dp[i][j]>=dp[i+1][j-1]+2) { if(dp[i][j]>dp[i+1][j-1]+2) str[i][j].clear(); dp[i][j]=dp[i+1][j-1]+2; for(int p=0;p<str[i+1][j-1].size();p++) { string ss = str[i+1][j-1][p]; if(std::find(str[i][j].begin(), str[i][j].end(), ss) == str[i][j].end()) str[i][j].push_back(ss); } } } } } return str[0][s.length()-1]; } };
