Giả sử có chuỗi S chỉ chứa '(' và ')', ta thêm số lượng ngoặc tối thiểu tại bất kỳ vị trí nào để chuỗi ngoặc kết quả hợp lệ. Chuỗi ngoặc hợp lệ nếu và chỉ nếu −
- Là chuỗi rỗng
- Có thể viết thành XY (X nối Y), với X, Y hợp lệ
- Có thể viết thành (A), với A hợp lệ.
Ví dụ chuỗi "()))((", cần thêm 4 ngoặc để hợp lệ.
Để giải quyết, ta làm theo các bước −
- nếu S rỗng, trả về 0
- count := 0, temp là mảng, temp_counter := 0
- với i trong S
- nếu i là ngoặc mở, thêm i vào temp
- ngược lại
- khi độ dài temp > 0 và phần tử cuối là ngoặc mở, xóa phần tử cuối temp, ngược lại thêm i vào temp
- trả về độ dài temp.
Xem triển khai sau −
Ví dụ
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("()))(("))Đầu vào
"()))(("Kết quả
4