Cho một chuỗi dấu ngoặc s gồm '(' và ')'. Hãy tìm số lượng dấu ngoặc tối thiểu cần thêm vào vị trí bất kỳ để chuỗi trở nên hợp lệ.
Ví dụ 1: s = "())" -> 1 (thêm 1 dấu '(' vào đầu)
Ví dụ 2: s = "(((" -> 3 (thêm 3 dấu ')' vào cuối)
Định Dạng Đầu Vào (Input)
Một dòng chứa chuỗi s
Định Dạng Đầu Ra (Output)
Một số nguyên duy nhất là số dấu ngoặc cần thêm
Ràng Buộc (Constraints)
1 <= s.length <= 1000
Ví Dụ Kiểm Thử Mẫu
Ví dụ 1:
Input:
"())"
Output:
1
Giải thích: Cần thêm 1 mở ngoặc
Ví dụ 2:
Input:
"((("
Output:
3
Giải thích: Cần thêm 3 đóng ngoặc
Gợi ý được sắp xếp theo cấp độ tiến dần. Hãy mở từng gợi ý khi bạn thực sự cần thêm định hướng.
Kỹ thuật Đếm Cân Bằng O(n) Thời Gian & O(1) Bộ Nhớ
Duy trì 2 biến đếm: openCount (số dấu mở ngoặc chưa ghép cặp) và addCount (số dấu mở ngoặc cần bù khi gặp đóng ngoặc lẻ). Kết quả là openCount + addCount.
Dữ liệu đầu vào (Input):
"())"
Kết quả kỳ vọng (Expected Output):
1
Dữ liệu đầu vào (Input):
"((("
Kết quả kỳ vọng (Expected Output):
3
Nhập STDIN của bạn (Mỗi dòng một tham số):
Bấm Chạy thử để kiểm tra các bộ test mẫu hoặc Nộp bài để chấm điểm chính thức.
Đang gửi mã và thực thi trên Sandbox Engine...
