โปรแกรมหาจำนวนวงเล็บสมดุลสูงสุดใน Python

สมมติว่าเรามีสตริงที่มีวงเล็บสมดุล "(" และ ")" เราต้องแยกเป็นจำนวนสูงสุดของกลุ่มที่สมดุล

ดังนั้น หากอินพุตเป็น "(()())()(())" ผลลัพธ์จะเป็น ['(()())', '()', '(())']

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• temp :=สตริงว่าง
• groups :=รายการใหม่
• นับ :=0
• สำหรับแต่ละอักขระ b ใน s ทำ
  • ถ้าการนับเท่ากับ 0 และขนาดของอุณหภูมิ> 0 แล้ว
    • ใส่ temp ที่ส่วนท้ายของกลุ่ม
    • temp :=สตริงว่าง
  • temp :=temp concatenate b
  • ถ้า b เหมือนกับ '(' แล้ว
    • นับ :=นับ + 1
  • มิฉะนั้น
    • นับ :=นับ - 1
• ใส่ temp ที่ส่วนท้ายของกลุ่ม
• คืนกลุ่ม

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

class Solution:
   def solve(self, s):
      temp = ''
      groups = []
      count = 0
      for b in s:
         if count == 0 and len(temp) > 0:
            groups.append(temp)
         temp = ''
         temp += b
         if b == '(':
            count += 1
         else:
            count -= 1
      groups.append(temp)
      return groups
s = "(()())()(())"
ob = Solution()
print(ob.solve(s))

อินพุต

"(()())()(())"

ผลลัพธ์

['(()())', '()', '(())']