Độ sâu lồng tối đa của hai chuỗi dấu ngoặc hợp lệ trong Python

Giả sử chúng ta có một chuỗi, chuỗi đó là một chuỗi trong ngoặc hợp lệ (ký hiệu là VPS) nếu và chỉ khi nó chỉ bao gồm các ký tự "(" và ")" và nó thỏa mãn các thuộc tính này -

• Đây là chuỗi trống hoặc

• Nó có thể được viết là AB, trong đó A và B là của VPS, hoặc

• Nó có thể được viết là (A), trong đó A là VPS.

Chúng tôi cũng có thể xác định độ sâu độ sâu lồng nhau (S) của bất kỳ VPS S nào như bên dưới -

• chiều sâu ("") =0

• độ sâu (A + B) =độ sâu tối đa (A), độ sâu (B), trong đó A và B là của VPS

• deep ("(" + A + ")") =1 + depth (A), trong đó A là VPS.

Nếu chúng ta có seq VPS, chúng ta phải chia nó thành hai dãy con A và B rời rạc, sao cho A và B là của VPS (và độ dài của A + độ dài của B =độ dài của seq). Bây giờ nếu chúng ta chọn bất kỳ A và B nào như vậy sao cho tối đa (độ sâu (A), độ sâu (B)) là giá trị nhỏ nhất có thể. Sau đó, chúng ta phải tìm một mảng câu trả lời (có độ dài của seq) mã hóa sự lựa chọn A và B như vậy:answer [i] =0 nếu seq [i] là một phần của A, nếu không thì trả lời [i] =1.

Vì vậy, nếu đầu vào là "() (()) ()", thì đầu ra sẽ là [1,1,1,0,1,0,1,1]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=độ dài của seq, res:=một mảng 0 có độ dài là n

• c1, c2:=0, 0

• cho tôi trong phạm vi từ 0 đến n - 1

  • nếu seq [i] =‘(’

    • nếu c1

  • nếu không thì

    • nếu c1> c2 thì giảm c1 đi 1, ngược lại giảm c2 đi 1 và res [i]:=1

• trả lại res

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

class Solution(object):
   def maxDepthAfterSplit(self, seq):
      n = len(seq)
      res = [0] *n
      c1,c2= 0,0
      for i in range(n):
         if seq[i] == '(':
            if c1<c2:
               c1+=1
         else:
            c2+=1
            res[i]=1
      else:
         if c1>c2:
            c1-=1
         else:
            c2-=1
            res[i]=1
   return res
ob = Solution()
print(ob.maxDepthAfterSplit("()(())()"))

Đầu vào

"()(())()"

Đầu ra

[1, 1, 1, 0, 1, 0, 1, 1]