Giả sử chúng ta có một chuỗi s với dấu ngoặc mở và đóng '(' và ')'. Có thể nói một chuỗi trong ngoặc đơn là cân bằng khi -
-
Bất kỳ dấu ngoặc đơn nào bên trái '(' có hai dấu ngoặc đơn bên phải liên tiếp tương ứng '))'.
-
Dấu ngoặc trái '(' phải đi trước hai dấu ngoặc phải liên tiếp tương ứng '))'.
Vì vậy, ví dụ, "())", "()) (())))" là cân bằng nhưng ") ()", "()))" thì không. Nếu chúng ta có chuỗi như vậy, chúng ta phải đếm số lượng dấu ngoặc (mở hoặc đóng) để làm cho chuỗi cân bằng.
Vì vậy, nếu đầu vào là s ="(())))))", thì đầu ra sẽ là 1 vì nếu chúng ta tách nó ra, chúng ta có thể nhận được "(())))))", vì vậy chúng ta cần một dấu ngoặc bên trái để tạo chuỗi "(()) ())))" để làm cho nó cân bằng.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
:=0, n:=kích thước của s
-
ret:=0, i:=0
-
trong khi tôi
-
nếu s [i] giống với '(', thì
-
-
:=o + 1
-
nếu không,
-
nếu i + 1
-
nếu o bằng 0 thì
-
ret:=ret + 1
-
-
nếu không,
-
-
-
-
:=o - 1
-
i:=i + 1
-
nếu không,
-
ret:=ret + 1
-
nếu o bằng 0 thì
-
ret:=ret + 1
-
-
nếu không,
-
-
-
:=o - 1
-
i:=i + 1
-
-
trả về ret + 2 * o
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
def solve(s):
o = 0
n = len(s)
ret = 0
i = 0
while i < n:
if s[i] == '(':
o += 1
else:
if i + 1 < n and s[i + 1] == ')':
if not o:
ret += 1
else:
o -= 1
i += 1
else:
ret += 1
if not o:
ret += 1
else:
o -= 1
i += 1
return ret + 2 * o
s = "(())))))"
print(solve(s)) Đầu vào
"(())))))"
Đầu ra
3