資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++中移除無效括號
假設我們有一串括號。我們必須移除最少數量的無效括號並返回格式良好的括號字串。因此，如果輸入類似於“()(()()”，則結果將是[“()()()”,“()(())”]。
為了解決這個問題，我們將遵循以下步驟：
定義一個名為solve()的方法，它將接收pos、left、right、l、r、字串陣列res和字串temp作為引數。
如果pos等於s的大小，則：
如果left等於0且right等於0，則：
如果(m[temp]不等於零)為假，則：
將temp插入res的末尾
m[temp] := 1
返回
如果s[pos]等於'('且right > 0，則：
呼叫solve(pos + 1, left, right - 1, l, r, res, temp + 空字串)
否則，如果s[pos]等於')'且left > 0，則：
呼叫solve(pos + 1, left - 1, right, l, r, res, temp + 空字串)
如果s[pos]等於'('，則：
呼叫solve(pos + 1, left, right, l + 1, r, res, temp + "(")
否則，如果s[pos]等於')'且l > r，則：
呼叫solve(pos + 1, left, right, l, r + 1, res, temp + ')')
如果s[pos]不等於'('且s[pos]不等於')'，則：
呼叫solve(pos + 1, left, right, l, r, res, temp + s[pos])
在主方法中執行以下操作：
建立一個數組res
l := 0, r := 0
初始化i := 0，當i < s的大小時，i遞增1：
如果s[i]等於'('，則：
r遞增1
否則，如果s[i]等於')'，則：
如果r不等於零，則r遞減1
否則l遞增1
呼叫函式solve(0,l,r,0,0,res)
返回res
示例
讓我們來看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
string s;
map <string ,int> m;
void solve(int pos, int left, int right,int l, int r, vector <string> &res, string temp=""){
if(pos == s.size()){
if(left==0 && right==0 && l==r){
if(!m[temp])
res.push_back(temp);
m[temp] = 1;
}
return;
}
if(s[pos] =='(' && right>0 ){
solve(pos+1,left,right-1,l,r,res,temp+"");
} else if(s[pos] ==')' && left>0) {
solve(pos+1,left-1,right,l,r,res,temp+"");
}
if(s[pos] =='(')solve(pos+1,left,right,l+1,r,res,temp+"(");
else if(s[pos] == ')' && l>r)solve(pos+1,left,right,l,r+1,res,temp+')');
if(s[pos]!='(' && s[pos]!=')')solve(pos+1,left,right,l,r,res,temp+s[pos]);
}
vector<string> removeInvalidParentheses(string s) {
vector <string > res;
int l = 0;
int r=0;
this->s = s;
for(int i =0;i<s.size();i++){
if(s[i] == '('){
r++;
} else if(s[i]==')') {
if(r)r--;
else l++;
}
}
solve(0,l,r,0,0,res);
return res;
}
};
main(){
Solution ob;
print_vector(ob.removeInvalidParentheses("()(()()"));
}輸入
“()(()()”
輸出
[()()(), ()(()), ]
276 次瀏覽
