โปรแกรมนับจำนวนวงเล็บที่ต้องลบน้อยที่สุดเพื่อให้สตริงถูกต้องใน Python

สมมติว่าเรามีสตริงวงเล็บ เราต้องเขียนฟังก์ชันคำนวณจำนวนวงเล็บน้อยที่สุดที่ต้องลบเพื่อให้สตริงถูกต้อง (วงเล็บเปิดแต่ละตัวมีวงเล็บปิดปิดท้าย)

ตัวอย่าง: "(()))(" ผลลัพธ์คือ 2 เพราะสตริงที่ถูกต้องคือ "(())" ลบ ")("

ขั้นตอนการแก้ปัญหา

1. กำหนด total = 0, temp = 0
2. สำหรับแต่ละ p ใน s:
   • ถ้า p == "(": total += 1
   • ถ้า p == ")" และ total != 0: total -= 1
   • อื่นๆ: temp += 1
3. คืนค่า total + temp

ตัวอย่างโค้ด Python

class Solution:
    def solve(self, s):
        total = 0
        temp = 0
        for p in s:
            if p == "(":
                total += 1
            elif p == ")" and total:
                total -= 1
            else:
                temp += 1
        return total + temp

ob1 = Solution()
string = "(()))("
print(ob1.solve(string))  # Output: 2

อินพุต / เอาต์พุต

Input: "(()))("

Output: 2