สมมติว่าเรามีสตริง S ของวงเล็บ '(' และ ')' เราเพิ่มจำนวนวงเล็บขั้นต่ำที่ตำแหน่งใดๆ เพื่อให้สตริงผลลัพธ์ในวงเล็บถูกต้อง สตริงวงเล็บจะใช้ได้ก็ต่อเมื่อ −
- เป็นสตริงว่าง
- สามารถเขียนเป็น XY (X ต่อด้วย Y) โดยที่ X และ Y เป็นสตริงที่ถูกต้อง
- สามารถเขียนเป็น (A) โดยที่ A เป็นสตริงที่ถูกต้อง
ดังนั้นหากสตริงเป็นแบบ "()))((" เราก็จำเป็นต้องเพิ่มวงเล็บอีก 4 อันเพื่อให้สตริงถูกต้อง
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ถ้า S ว่างเปล่า ให้คืนค่า 0
- count :=0, temp เป็นอาร์เรย์ temp_counter :=0
- สำหรับฉันใน S
- ถ้าฉันเปิดวงเล็บ ให้ใส่ i ลงใน temp
- อย่างอื่น
- เมื่อความยาวของ temp> 0 และองค์ประกอบสุดท้ายของวงเล็บเปิดอยู่ ให้ลบองค์ประกอบสุดท้ายของ temp ออก ไม่เช่นนั้นให้ใส่ i ลงใน temp
- คืนค่าขนาดของอุณหภูมิ
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
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("()))((")) อินพุต
"()))((" ผลลัพธ์
4
