A. Déjà Vu
|
|
| Quán chỗ nào thoáng vậy bạn? Phải ở hồ Bán Nguyệt quận 7 không? |
Tóm tắt: bạn cần chèn đúng 1 ký tự a vào xâu $s$ sao cho xâu mới tạo thành không phải là một xâu palindrome. Nếu không thể thực hiện, in ra NO.
Hướng giải:
- Nếu xâu $s$ chỉ toàn ký tự a, khi đó bạn chèn ký tự a vào chỗ nào cũng sẽ tạo thành một xâu palindrome. Do đó, trường hợp này là trường hợp duy nhất không thể biến đổi.
- Với các trường hợp còn lại, ta cần xác định vị trí chèn ký tự a thích hợp. Nếu duyệt qua từng vị trí $i\ (0 \leq i \leq |s|)$ sau đó kiểm tra palindrome sẽ đẩy độ phức tạp bài toán lên $O(n^2)$. Đến đây ta cần quan sát:
- Giả sử xâu $s$ ban đầu đã là palindrome. Khi đó chèn ký tự a vào đầu / đuôi xâu sẽ tạo ra một xâu không phải palindrome.
- Xâu $s$ ban đầu không phải palindrome và bắt đầu bằng ký tự a. Khi đó, nếu chèn a vào đuôi xâu có thể tạo ra một xâu palindrome. Do vậy, trong trường hợp này ta phải xét xem xâu mới chèn có phải là palindrome hay không. Tương tự với trường hợp kết thúc bằng ký tự a.
Tóm lại, trừ trường hợp xâu toàn ký tự a cho kết quả NO ra, các trường hợp khác ta sẽ kiểm tra xem $a + s$ (chèn a vào đầu xâu $s$) và $s + a$ (chèn a vào đuôi xâu $s$), chỉ cần 1 trong 2 xâu không phải palindrome thì ta cứ in ra là xong.
Happy coding!
No comments:
Post a Comment