โจทย์: กำหนดสตริงวงเล็บ '(' และ ')' หาจำนวนวงเล็บน้อยที่สุดที่ต้องเพิ่มเพื่อให้ถูกต้อง
ตัวอย่าง
Input: "()))(("
Output: 4
อัลกอริทึม: Stack / Counter
- ใช้ตัวนับ
balanceแทนจำนวน '(' ที่ยังไม่จับคู่ - เจอ '(' → balance++
- เจอ ')' → ถ้า balance > 0 ให้ balance--, ไม่งั้นต้องเพิ่ม '(' (ans++)
- ท้ายสุด ต้องเพิ่ม ')' เท่ากับ balance ที่เหลือ
ตัวอย่างโค้ด Python (ปรับปรุงจากต้นฉบับ)
class Solution:
def minAddToMakeValid(self, S):
if not S:
return 0
balance = 0 # จำนวน '(' ที่ยังไม่จับคู่
additions = 0 # จำนวนที่ต้องเพิ่ม
for ch in S:
if ch == '(':
balance += 1
else: # ch == ')'
if balance > 0:
balance -= 1 # จับคู่กับ '(' ก่อนหน้า
else:
additions += 1 # ต้องเพิ่ม '('
# เพิ่ม ')' สำหรับ '(' ที่เหลือ
return additions + balance
# ทดสอบ
ob = Solution()
print(ob.minAddToMakeValid("()))((")) # Output: 4
ตัวอย่าง Input/Output
Input: "()))(("
Output: 4
ความซับซ้อน: Time O(n), Space O(1) - ดีกว่าวิธีใช้ stack จริง
