ตรวจสอบว่าตัวอักษรในสตริงเป็นพาลินโดรมหรือไม่ (O(1) space) ใน Python

ปัญหา

ให้สตริง s (อาจมีตัวเลข/สัญลักษณ์) ตรวจสอบว่า ตัวอักษรภาษาอังกฤษพิมพ์เล็ก ที่อยู่ในสตริงเป็นพาลินโดรมหรือไม โดยใช้พื้นที่เพิ่มเติม O(1)

ตัวอย่าง

s = "ra$5ce58car" → ตัวอักษร: r a c e c a r → พาลินโดรม → True

แนวคิดการแก้ปัญหา (Two Pointers)

1. ใช้ pointer ซ้าย (left) และขวา (right)
2. ขยับ left ไปขวาจนเจอตัวอักษร a-z
3. ขยับ right ไปซ้ายจนเจอตัวอักษร a-z
4. เปรียบเทียบ ถ้าไม่เท่ากัน → False
5. ทำซ้ำจน left >= right

โค้ดตัวอย่าง

def solve(s):
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not ('a' <= s[left] <= 'z'):
            left += 1
        while left < right and not ('a' <= s[right] <= 'z'):
            right -= 1
        if left < right and s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

print(solve("ra$5ce58car"))  # True

อินพุต / เอาต์พุต

Input:  "ra$5ce58car"
Output: True