Thêm tối thiểu để làm cho dấu ngoặc đơn hợp lệ trong Python

Giả sử chúng ta có một chuỗi S gồm các dấu ngoặc đơn '(' và ')', chúng ta thêm số lượng tối thiểu các dấu ngoặc vào bất kỳ vị trí nào, để chuỗi ngoặc đơn thu được là hợp lệ. Chuỗi dấu ngoặc đơn hợp lệ nếu và chỉ khi -

• Đây là một chuỗi trống
• Nó có thể được viết là XY (X được nối với Y), trong đó X và Y là các chuỗi hợp lệ
• Nó có thể được viết là (A), trong đó A là một chuỗi hợp lệ.

Vì vậy, nếu chuỗi giống như "())) ((", thì chúng ta cần thêm 4 dấu ngoặc đơn nữa để làm cho chuỗi hợp lệ.

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

• nếu S trống, thì trả về 0
• count:=0, temp là một mảng, temp_counter:=0
• cho tôi trong S
  • nếu tôi đang mở ngoặc đơn, thì hãy chèn tôi vào tạm thời
  • ngược lại
    • khi độ dài của tạm thời> 0 và phần tử cuối cùng của mở ngoặc đơn, thì hãy xóa phần tử cuối cùng của tạm thời, nếu không hãy chèn i vào tạm thời
• trả lại kích thước của nhiệt độ.

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

Ví dụ

class Solution:
   def minAddToMakeValid(self, S):
      if not S:
         return 0
      count = 0
      temp = []
      temp_counter = 0
      for i in S:
         if i =='(':
            temp.append(i)
         else:
            if len(temp)>0 and temp[len(temp)-1] =='(':
               temp.pop(len(temp)-1)
            else:
               temp.append(i)
      return len(temp)
ob = Solution()
print(ob.minAddToMakeValid("()))(("))

Đầu vào

"()))(("

Đầu ra

4