# Lời giải bài Decode

## Tác giả: Trương Hoàng Quân, i2124

## 1. Thuật toán ngây thơ

- Đề nói gì làm nấy, tuần tự đảo các đoạn trong ngoặc.
- Độ phức tạp: $O(n ^ 2)$

## 2. Cải tiến

- Việc đảo ngược một đoạn của xâu tốn $O(n)$, ta sẽ tìm cách bỏ đi thao tác này. Khi đảo ngược một đoạn, ta có thể đi ngược từ vị trí cuối đoạn về trí đầu đoạn và xuất đáp án. Như vậy nhiệm vụ bây giờ là xác định được vị trí cuối của một đoạn.
- Duyệt qua xâu, khi gặp '(' ta sẽ đẩy vào stack, khi gặp ')' thì tạo ra một cặp ngoặc tương ứng với ngoặc mở '(' cuối cùng trong stack. Ghi nhận lại 2 giá trị này.
- Duyệt qua xâu một lần nữa để xuất đáp án. Khi này nếu gặp một ngoặc mở '(', ta đi tới vị trí tương ứng của ngoặc đóng ')' và duyệt ngược lại xuất đáp án. Trong lúc này, nếu gặp ngoặc đóng ')', ta nhảy tới vị trí ngoặc mở '(' tương ứng và duyệt xuôi để xuất đáp án. Lặp đi lặp lại các thao tác này.
### Độ phức tạp: $O(n)$
### Code mẫu: [Link](https://ideone.com/ZvX8GJ)