Giả sử chúng ta có một chuỗi ký tự tiếng Anh '(', ')' và chữ thường. Chúng ta phải loại bỏ số lượng tối thiểu các dấu ngoặc đơn ('(' hoặc ')', ở bất kỳ vị trí nào) để chuỗi ngoặc đơn kết quả là hợp lệ và trả về bất kỳ chuỗi hợp lệ nào. Chuỗi dấu ngoặc đơn hợp lệ khi tất cả các tiêu chí này được đáp ứng -
-
Đây là chuỗi trống, chỉ chứa các ký tự viết thường hoặc
-
Nó có thể được viết dưới dạng AB (A nối với B), trong đó A và B là các chuỗi hợp lệ, hoặc
-
Nó có thể được viết dưới dạng (A), trong đó A là một chuỗi hợp lệ.
Vì vậy, nếu đầu vào là “a) b (c) d”, thì đầu ra sẽ là “ab (c) d”
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một ngăn xếp
-
cho tôi trong phạm vi từ 0 đến kích thước của s
-
if s [i] =‘(’, sau đó chèn i vào st
-
ngược lại khi s [i] là ‘)’ thì
-
nếu ngăn xếp không trống, thì bật từ ngăn xếp, nếu không thì s [i] =‘*’
-
-
-
trong khi st không trống,
-
s [phần tử trên cùng của ngăn xếp] =‘*’
-
bật ra từ ngăn xếp
-
-
ans:=chuỗi trống
-
cho tôi trong phạm vi từ 0 đến kích thước của s-1
-
nếu s [i] không phải là ‘*’ thì ans:=ans + s [i]
-
-
trả lại ans
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string minRemoveToMakeValid(string s) {
stack <int> st;
for(int i = 0; i < s.size(); i++){
if(s[i] == '(')st.push(i);
else if(s[i] == ')'){
if(!st.empty())st.pop();
else s[i] = '*';
}
}
while(!st.empty()){
s[st.top()] = '*';
st.pop();
}
string ans = "";
for(int i = 0; i < s.size(); i++){
if(s[i] != '*')ans += s[i];
}
return ans;
}
};
main(){
Solution ob;
cout << (ob.minRemoveToMakeValid("a)b(c)d"));
} Đầu vào
"a)b(c)d"
Đầu ra
ab(c)d