Valid Palindrome

Bài toán

Một cụm từ là Palindrome nếu sau khi chuyển tất cả chữ cái in hoa thành in thường và xóa bỏ các ký tự không phải chữ-số (non-alphanumeric), nó đọc xuôi hay đọc ngược đều giống nhau.

Cho một chuỗi s, trả về true nếu nó là Palindrome, ngược lại false.

Ví dụ:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Giải thích: "amanaplanacanalpanama" là chuỗi đối xứng.

Phân Tích & Tiếp Cận

Cách 1: Reverse String

1. Làm sạch chuỗi (xóa ký tự đặc biệt, lowercase).
2. Tạo chuỗi đảo ngược.
3. So sánh chuỗi sạch và chuỗi đảo ngược.

function isPalindrome(s: string): boolean {
    const cleanStr = s.replace(/[^a-zA-Z0-9]/g, '').toLowerCase();
    const reverseStr = cleanStr.split('').reverse().join('');
    return cleanStr === reverseStr;
}

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$ (Tạo chuỗi mới).

Cách 2: Two Pointers (Tối ưu bộ nhớ)

Ta không cần tạo chuỗi mới. Ta dùng 2 con trỏ:

• left bắt đầu từ đầu chuỗi (0).
• right bắt đầu từ cuối chuỗi (len - 1).

Di chuyển chúng dần vào giữa:

• Nếu s[left] không phải chữ/số -> left++.
• Nếu s[right] không phải chữ/số -> right--.
• Nếu cả 2 đều là chữ/số:
  • So sánh s[left].toLowerCase() với s[right].toLowerCase().
  • Khác nhau -> return false.
  • Giống nhau -> left++, right--.

function isPalindrome(s: string): boolean {
    let l = 0;
    let r = s.length - 1;

    while (l < r) {
        // Bỏ qua ký tự không phải chữ/số
        while (l < r && !isAlphaNumeric(s[l])) {
            l++;
        }
        while (r > l && !isAlphaNumeric(s[r])) {
            r--;
        }

        if (s[l].toLowerCase() !== s[r].toLowerCase()) {
            return false;
        }

        l++;
        r--;
    }
    return true;
}

// Helper check ký tự
function isAlphaNumeric(char: string): boolean {
    const code = char.charCodeAt(0);
    return (
        (code >= 48 && code <= 57) || // 0-9
        (code >= 65 && code <= 90) || // A-Z
        (code >= 97 && code <= 122)   // a-z
    );
}

• Time Complexity: $O(n)$ - Duyệt mỗi ký tự tối đa 1 lần.
• Space Complexity: $O(1)$ - Không tạo chuỗi hay cấu trúc dữ liệu mới.

Pattern Nhận Diện

Two Pointers (Đối nghịch): Khi cần so sánh hoặc thao tác các phần tử ở hai đầu mảng/chuỗi và di chuyển dần vào giữa. Ứng dụng: Kiểm tra đối xứng, Đảo ngược chuỗi, Tìm cặp số trong mảng đã sắp xếp.