Hướng giải của Kiểm tra xâu đối xứng

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Lời giải: Kiểm tra xâu đối xứng

Phân tích

Dùng hai con trỏ, một bên trái và một bên phải, so sánh từng cặp ký tự đối xứng. Nếu tất cả các cặp đều khớp thì xâu là palindrome.

Độ phức tạp

Thời gian: O(N)
Không gian: O(1)

Code mẫu C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int l = 0, r = s.size() - 1;  // Con trỏ trái và phải
    while (l < r) {
        if (s[l] != s[r]) {
            // Có cặp ký tự không khớp -> không phải palindrome
            cout << "NO" << endl;
            return 0;
        }
        l++;  // Di chuyển con trỏ trái vào trong
        r--;  // Di chuyển con trỏ phải vào trong
    }
    // Tất cả các cặp đều khớp -> palindrome
    cout << "YES" << endl;
    return 0;
}

Giải thích

Con trỏ l bắt đầu từ đầu xâu, con trỏ r bắt đầu từ cuối xâu.
Mỗi bước so sánh s[l] với s[r]. Nếu khác nhau, kết luận không phải palindrome ngay.
Vòng lặp dừng khi l >= r, tức đã so sánh hết hoặc chỉ còn ký tự ở giữa.

Nhận xét

Không có ý kiến tại thời điểm này.