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
Hướng giải:
-
Nếu xâu
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í
sau đó kiểm tra palindrome sẽ đẩy độ phức tạp bài toán lên . Đến đây ta cần quan sát: -
Giả sử xâu
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
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
Happy coding!
No comments:
Post a Comment