Giả sử chúng ta có một chuỗi s với dấu ngoặc đơn '(', ')' và các ký tự tiếng Anh viết thường. Chúng tôi phải xóa số lượng tối thiểu các dấu ngoặc đơn ('(' hoặc ')', khỏi bất kỳ vị trí nào) để chuỗi dấu ngoặc đơn kết quả là hợp lệ và cuối cùng phải trả về bất kỳ chuỗi hợp lệ nào. Ở đây, chuỗi dấu ngoặc đơn hợp lệ khi tất cả các tiêu chí này được đáp ứng -
-
Chuỗi trống và chỉ chứa các ký tự viết thường hoặc
-
Chuỗi có thể được viết là AB (A được nối với B), trong đó A và B là các chuỗi hợp lệ hoặc
-
Chuỗi 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à s ="m) n (o) p", thì đầu ra sẽ là "mn (o) p"
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
stack:=một danh sách mới
-
indexes:=a new set
-
i:=0
-
đối với mỗi c trong s, thực hiện
-
nếu c giống với '(', thì
-
đẩy tôi vào ngăn xếp
-
-
ngược lại khi c giống với ')' thì
-
nếu kích thước của ngăn xếp bằng 0, thì
-
chèn i vào các chỉ mục
-
-
nếu không,
-
bật ra từ ngăn xếp
-
-
i:=i + 1
-
-
-
ret:=chuỗi trống
-
indexes:=lưu trữ tất cả các phần tử vào chỉ mục
-
đối với tôi trong phạm vi từ 0 đến kích thước của s-1, hãy thực hiện
-
nếu tôi không có trong chỉ mục, thì
-
ret:=ret + s [i]
-
-
-
trả lại ret
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
def solve(s):
stack = []
indexes = set()
i = 0
for c in s:
if c == '(':
stack.append(i)
elif c == ')':
if len(stack) == 0:
indexes.add(i)
else:
stack.pop()
i += 1
ret = ''
indexes = indexes.union(stack)
for i in range(len(s)):
if i not in indexes:
ret += s[i]
return ret
s = "m)n(o)p"
print(solve(s)) Đầu vào
"m)n(o)p"
Đầu ra
mn(o)p