Kiểm tra chuỗi có tạo thành palindrome chỉ xét chữ cái trong Python (O(1) space)

Cho chuỗi s có thể chứa chữ thường, số, ký tự đặc biệt. Chỉ xét các chữ cái thường, kiểm tra xem chúng có tạo thành palindrome hay không, với ràng buộc không dùng bộ nhớ thêm (O(1) extra space).

Ví dụ: "ra$5ce58car" → các chữ cái tạo thành "racecar" → True.

Giải thuật

• Dùng hai con trỏ left (từ đầu) và right (từ cuối).
• Hàm first_letter_index tìm chỉ số chữ cái đầu tiên từ left đến right.
• Hàm last_letter_index tìm chỉ số chữ cái cuối cùng từ right về left.
• So sánh hai ký tự tại vị trí tìm được, nếu khác → False.
• Di chuyển con trỏ, lặp lại cho đến khi left >= right.

Mã ví dụ

def first_letter_index(s, left, right):
    index = -1
    for i in range(left, right + 1):
        if 'a' <= s[i] <= 'z':
            index = i
            break
    return index

def last_letter_index(s, left, right):
    index = -1
    for i in range(left, right - 1, -1):
        if 'a' <= s[i] <= 'z':
            index = i
            break
    return index

def solve(s):
    left = 0
    right = len(s) - 1
    flag = True
    for _ in range(len(s)):
        left = first_letter_index(s, left, right)
        right = last_letter_index(s, right, left)
        if right < 0 or left < 0:
            break
        if s[left] == s[right]:
            left += 1
            right -= 1
            continue
        flag = False
        break
    return flag

s = "ra$5ce58car"
print(solve(s))

Đầu vào

"ra$5ce58car"

Đầu ra

True