Xâu đối xứng (Palindrome), số đối xứng và bài toán đảo chữ (Anagram): C++, Python

Xâu đối xứng (Palindrome) là gì và cách kiểm tra bằng hai con trỏ

Các bản C++ và Python dưới đây được đối chiếu trên đầu vào ASCII. std::string UTF-8 đếm byte, còn Python str đếm mã Unicode; kiểm tra đối xứng cho tiếng Việt cần xác định cách chuẩn hóa và đơn vị ký tự trước.

Một xâu ký tự s độ dài n được gọi là xâu đối xứng (palindrome) nếu ký tự đầu bằng ký tự cuối, ký tự thứ hai bằng ký tự kế cuối, và cứ thế đối xứng qua tâm: s[i] == s[n - 1 - i] với mọi 0 ≤ i < n.

Cách viết ngắn nhất mà nhiều bạn thường nghĩ tới là tạo một xâu mới đảo ngược rev (ví dụ s[::-1] trong Python) rồi kiểm tra s == rev. Cách này chạy đúng nhưng có hai nhược điểm:

1. Phải cấp phát thêm O(n) bộ nhớ phụ để lưu bản sao đảo ngược.
2. Luôn phải chép toàn bộ n ký tự ngay cả khi cặp ký tự đầu–cuối s[0] và s[n - 1] đã khác nhau ngay từ bước đầu tiên!

Giải pháp chuẩn mực trong lập trình thuật toán và phỏng vấn là dùng kỹ thuật hai con trỏ chạy ngược chiều nhau ngay trên xâu gốc:

• Đặt con trỏ trái ở đầu xâu l = 0 và con trỏ phải ở cuối xâu r = n - 1.
• Trong khi l nhỏ hơn r:
  • So sánh s[l] với s[r]. Nếu khác nhau, kết luận ngay xâu không đối xứng (false) và dừng hàm.
  • Nếu bằng nhau, nhích hai con trỏ tiến vào tâm: ++l và --r.
• Khi vòng lặp kết thúc (l ≥ r), mọi cặp đối xứng đã khớp hết nên trả về true.

Bảng so sánh hai cách tiếp cận trên xâu độ dài n (xem thêm cách đánh giá tại bài độ phức tạp thuật toán Big-O):

Biến thể thực tế: Kiểm tra câu đối xứng bỏ qua dấu câu và chữ hoa/thường

Trong các bài phỏng vấn thực tế (như bài Valid Palindrome trên LeetCode), đầu vào không chỉ gồm chữ cái thường liền mạch mà là cả một câu có khoảng trắng, dấu phẩy, dấu hai chấm và chữ in hoa, ví dụ: "A man, a plan, a canal: Panama"

Đề bài yêu cầu chỉ xét các chữ cái và chữ số (alphanumeric) và không phân biệt chữ hoa/thường. Nếu lọc hết các ký tự hợp lệ ra một xâu tạm mới rồi mới kiểm tra, bạn lại tốn O(n) bộ nhớ phụ.

Thay vào đó, ta giữ nguyên bộ khung hai con trỏ l, r và chỉ thêm hai vòng lặp while nhỏ bên trong để nhảy qua các ký tự dấu câu/khoảng trắng:

1. Trong khi l < r và s[l] không phải chữ/số (!isalnum(s[l])), ta tăng ++l để bỏ qua.
2. Trong khi l < r và s[r] không phải chữ/số (!isalnum(s[r])), ta giảm --r để bỏ qua.
3. Khi cả s[l] và s[r] đều đã đứng ở ký tự hợp lệ, ta so sánh tolower(s[l]) với tolower(s[r]).

#include <cctype>
#include <iostream>
#include <string>

using namespace std;

// 1. Kiểm tra xâu đối xứng cơ bản bằng hai con trỏ: O(n) thời gian, O(1) bộ nhớ
bool la_xau_doi_xung(const string& s) {
    int l = 0;
    int r = static_cast<int>(s.size()) - 1;
    while (l < r) {
        if (s[l] != s[r]) {
            return false;
        }
        ++l;
        --r;
    }
    return true;
}

// 2. Kiểm tra câu đối xứng khi bỏ qua dấu câu/khoảng trắng và không phân biệt hoa/thường
bool la_cau_doi_xung(const string& s) {
    int l = 0;
    int r = static_cast<int>(s.size()) - 1;
    while (l < r) {
        while (l < r && !isalnum(static_cast<unsigned char>(s[l]))) ++l;
        while (l < r && !isalnum(static_cast<unsigned char>(s[r]))) --r;
        if (tolower(static_cast<unsigned char>(s[l])) != tolower(static_cast<unsigned char>(s[r]))) {
            return false;
        }
        ++l;
        --r;
    }
    return true;
}

int main() {
    cout << la_xau_doi_xung("racecar") << " " << la_xau_doi_xung("abca") << " ";
    cout << la_cau_doi_xung("A man, a plan, a canal: Panama") << " " << la_cau_doi_xung("race a car") << "\n";
    return 0;
}

def la_xau_doi_xung(s: str) -> bool:
    """Kiểm tra xâu đối xứng bằng hai con trỏ trong O(n) thời gian, O(1) bộ nhớ phụ."""
    l, r = 0, len(s) - 1
    while l < r:
        if s[l] != s[r]:
            return False
        l += 1
        r -= 1
    return True


def la_cau_doi_xung(s: str) -> bool:
    """Kiểm tra câu đối xứng bỏ qua dấu câu/khoảng trắng và không phân biệt hoa/thường."""
    l, r = 0, len(s) - 1
    while l < r:
        while l < r and not s[l].isalnum():
            l += 1
        while l < r and not s[r].isalnum():
            r -= 1
        if s[l].lower() != s[r].lower():
            return False
        l += 1
        r -= 1
    return True


if __name__ == "__main__":
    kq = [
        1 if la_xau_doi_xung("racecar") else 0,
        1 if la_xau_doi_xung("abca") else 0,
        1 if la_cau_doi_xung("A man, a plan, a canal: Panama") else 0,
        1 if la_cau_doi_xung("race a car") else 0,
    ]
    print(*kq)

Chương trình in ra 1 0 1 0 tương ứng với:

• "racecar" → 1 (đối xứng)
• "abca" → 0 (tại l = 1, r = 2 có 'b' != 'c' nên dừng ngay)
• "A man, a plan, a canal: Panama" → 1 (sau khi bỏ dấu câu và đổi chữ thường là "amanaplanacanalpanama" đối xứng hoàn hảo)
• "race a car" → 0 (sau khi bỏ khoảng trắng là "raceacar" không đối xứng).

Kiểm tra số nguyên đối xứng không cần đổi sang xâu

Phần đảo toàn bộ số trong code giả định 0 ≤ n ≤ 2³¹ - 1, dùng long long cho số đảo để không tràn. Nếu nhận toàn miền long long, cần kiểm tra trước phép nhân hoặc chỉ đảo một nửa số. Một số nguyên được gọi là số đối xứng (palindrome number) nếu các chữ số của nó đọc xuôi hay ngược đều như nhau, ví dụ 12321, 7, 4004. Lưu ý:

• Mọi số âm (như -121) đều không phải số đối xứng vì đọc ngược sẽ thành 121-.
• Các số tận cùng bằng 0 (như 12310, khác số 0) không bao giờ đối xứng vì chữ số đầu tiên không thể là 0.

Để kiểm tra số nguyên n ≥ 0 có đối xứng không mà không cần đổi sang xâu ký tự, ta dùng phép chia lấy dư % 10 và chia nguyên / 10 để xây dựng số đảo ngược dao:

• Ở mỗi bước, chữ số hàng đơn vị của n là d = n % 10.
• Ta đẩy d vào cuối biến dao bằng công thức: dao = dao * 10 + d, rồi bỏ chữ số cuối của n bằng n /= 10.

Hãy xem bảng chạy từng bước với n = 12321 (lưu ban_dau = 12321, khởi tạo dao = 0):

Kết thúc vòng lặp, dao == ban_dau == 12321 nên 12321 là số đối xứng!

Mở rộng: Bài toán kiểm tra hai xâu đảo chữ (Anagram) trong O(n)

Một bài toán chị em luôn đi cặp với Palindrome trong các bộ đề xử lý xâu ký tự là kiểm tra hai xâu đảo chữ (Valid Anagram):

• Hai xâu s và t được gọi là đảo chữ (anagram) của nhau nếu ta có thể tráo đổi vị trí các ký tự của s để tạo thành t. Ví dụ: "listen" và "silent" là anagram; "rat" và "car" không phải là anagram.
• Điều kiện cần và đủ để s và t là anagram của nhau là: chúng có cùng độ dài và tần suất xuất hiện của từng chữ cái trong hai xâu hoàn toàn bằng nhau.

Nếu bạn dùng hàm sắp xếp sort(s) và sort(t) rồi so sánh s == t, độ phức tạp sẽ là O(n log n). Ta có thể làm tốt hơn hẳn trong thời gian tuyến tính O(n) và bộ nhớ O(1) chỉ bằng một mảng đếm dem[26], với điều kiện cả hai xâu chỉ có các chữ ASCII thường a..z:

1. Nếu s.size() != t.size(), trả về false ngay lập tức.
2. Tạo mảng dem[26] khởi tạo bằng 0. Duyệt i từ 0 đến n - 1:
   • Với ký tự s[i], ta cộng 1 vào ô tương ứng: ++dem[s[i] - 'a'].
   • Với ký tự t[i], ta trừ 1 ở ô tương ứng: --dem[t[i] - 'a'].
3. Sau vòng lặp, nếu mọi chữ cái ở hai xâu xuất hiện với số lần bằng nhau thì tất cả 26 ô của dem phải triệt tiêu về đúng bằng 0!

#include <iostream>
#include <limits>
#include <string>
#include <vector>

using namespace std;

// 1. Kiểm tra số nguyên đối xứng bằng cách đảo chữ số toán học (không đổi sang xâu)
bool la_so_doi_xung(long long n) {
    if (n < 0) return false;
    long long ban_dau = n;
    long long dao = 0;
    while (n > 0) {
        long long chu_so = n % 10;
        if (dao > (numeric_limits<long long>::max() - chu_so) / 10) return false;
        dao = dao * 10 + chu_so;
        n /= 10;
    }
    return dao == ban_dau;
}

// 2. Kiểm tra hai xâu đảo chữ (Anagram) bằng mảng tần suất 26 chữ cái trong O(n)
bool la_anagram(const string& s, const string& t) {
    if (s.size() != t.size()) return false;
    vector<int> dem(26, 0);
    for (size_t i = 0; i < s.size(); ++i) {
        ++dem[s[i] - 'a'];
        --dem[t[i] - 'a'];
    }
    for (int c : dem) {
        if (c != 0) return false;
    }
    return true;
}

int main() {
    cout << la_so_doi_xung(12321) << " " << la_so_doi_xung(12310) << " " << la_so_doi_xung(-121) << " ";
    cout << la_anagram("listen", "silent") << " " << la_anagram("rat", "car") << "\n";
    return 0;
}

def la_so_doi_xung(n: int) -> bool:
    """Kiểm tra số nguyên đối xứng bằng phép chia lấy dư, không đổi sang xâu."""
    if n < 0:
        return False
    ban_dau = n
    dao = 0
    while n > 0:
        dao = dao * 10 + (n % 10)
        n //= 10
    return dao == ban_dau


def la_anagram(s: str, t: str) -> bool:
    """Kiểm tra hai xâu đảo chữ (Anagram) bằng mảng đếm 26 chữ cái trong O(n)."""
    if len(s) != len(t):
        return False
    dem = [0] * 26
    base = ord("a")
    for ch_s, ch_t in zip(s, t):
        dem[ord(ch_s) - base] += 1
        dem[ord(ch_t) - base] -= 1
    return all(c == 0 for c in dem)


if __name__ == "__main__":
    kq = [
        1 if la_so_doi_xung(12321) else 0,
        1 if la_so_doi_xung(12310) else 0,
        1 if la_so_doi_xung(-121) else 0,
        1 if la_anagram("listen", "silent") else 0,
        1 if la_anagram("rat", "car") else 0,
    ]
    print(*kq)

Chương trình in ra 1 0 0 1 0 tương ứng với: 12321 (1), 12310 (0), -121 (0), cặp "listen" / "silent" (1) và cặp "rat" / "car" (0).

Lỗi hay gặp

Luyện ngay trên Big-O Coding

Thực hành ngay kỹ thuật kiểm tra xâu đối xứng, số đối xứng và mảng đếm tần suất trên hệ thống Big-O Coding:

Câu hỏi thường gặp

Nguồn tham khảo

• cppreference: std::isalnum, std::tolower
• Python Documentation: String Methods (isalnum, lower)
• CSES Competitive Programmer's Handbook — String Algorithms