ความลึกสูงสุดของการซ้อนสองวงเล็บในวงเล็บที่ถูกต้องใน Python

สมมติว่าเรามีสตริง สตริงนั้นเป็นสตริงในวงเล็บที่ถูกต้อง (แสดง VPS) หากประกอบด้วยอักขระ "(" และ ")" เท่านั้น และเป็นไปตามคุณสมบัติเหล่านี้ -

• เป็นสตริงว่างหรือ

• สามารถเขียนเป็น AB โดยที่ A และ B เป็น VPS หรือ

• สามารถเขียนเป็น (A) โดยที่ A คือ VPS

นอกจากนี้เรายังสามารถกำหนดความลึกของรัง (S) ของ VPS S ใด ๆ ดังด้านล่าง -

• ความลึก ("") =0

• ความลึก (A + B) =ความลึกสูงสุด (A), ความลึก (B) โดยที่ A และ B คือ VPS

• ความลึก ("(" + A + ")") =1 + ความลึก (A) โดยที่ A คือ VPS

ถ้าเรามี VPS seq เราต้องแยกมันออกเป็นสองส่วนย่อยที่ไม่ต่อเนื่องกัน A และ B โดยที่ A และ B เป็น VPS (และความยาวของ A + ความยาวของ B =ความยาวของ seq) ตอนนี้ถ้าเราเลือก A และ B ใด ๆ เช่น max(ความลึก(A), ความลึก (B)) เป็นค่าต่ำสุดที่เป็นไปได้ จากนั้นเราต้องหาอาร์เรย์คำตอบ (ความยาวของลำดับ) ที่เข้ารหัสตัวเลือก A และ B:answer[i] =0 ถ้า seq[i] เป็นส่วนหนึ่งของ A ไม่เช่นนั้น answer[i] =1.

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

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

• n :=ความยาวของ seq, res :=อาร์เรย์ของ 0s ที่มีความยาว n

• c1, c2 :=0, 0

• สำหรับฉันอยู่ในช่วง 0 ถึง n – 1

  • ถ้า seq[i] ='('

    • ถ้า c1

  • อย่างอื่น

    • ถ้า c1> c2 แล้วลด c1 ลง 1 มิฉะนั้น ลด c2 ลง 1 และ res[i]:=1

• ผลตอบแทน

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

ตัวอย่าง

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("()(())()"))

อินพุต

"()(())()"

ผลลัพธ์

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