LeetCode #125 Valid Palindrome: กรองก่อนหรือเดินสองด้าน แบบไหนเหมาะกว่า

Valid Palindrome ให้ตรวจ string หลังแปลงตัวอักษรเป็น lowercase และตัดอักขระที่ไม่ใช่ตัวอักษรหรือตัวเลขออก เช่น A man, a plan, a canal: Panama ต้องได้ true ข้อนี้ดูง่าย แต่เป็นสนามฝึกที่ดีสำหรับ tradeoff ระหว่างความอ่านง่ายกับพื้นที่เสริมครับ

วิธี 1: Normalize แล้วกลับด้าน

สร้าง string ใหม่จากอักขระที่ isalnum() แล้วใช้ casefold() จากนั้นเทียบกับ normalized[::-1] นี่เป็นคำตอบที่สั้นและอธิบายง่าย เวลา O(n) และพื้นที่ O(n) เหมาะกับงานทั่วไปเมื่อ input ไม่ใหญ่และความชัดสำคัญกว่า allocation

วิธี 2: Two pointers

ตั้ง pointer ซ้าย/ขวา ข้ามอักขระที่ไม่เกี่ยวข้อง แล้วเทียบตัวที่เหลือทีละคู่ ใช้เวลา O(n) และพื้นที่ O(1) จึงเป็นคำตอบแนะนำสำหรับโจทย์สัมภาษณ์ เพราะแสดง invariant ชัดว่า “ทุกคู่ด้านนอกที่ผ่านมาตรงกันแล้ว”

วิธี 3: Deque จากข้อมูลที่ normalize

ใส่อักขระลง deque แล้วดึงหัว/ท้ายมาเทียบ วิธีนี้ยังใช้พื้นที่ O(n) แต่แยกขั้น preprocessing จาก comparison และต่อยอดเมื่อข้อมูลมาจาก iterator ได้ง่ายกว่า ถึงอย่างนั้นมันซับซ้อนเกินจำเป็นสำหรับ string ที่อยู่ใน memory แล้ว

from collections import deque
import unittest


def by_reverse(text: str) -> bool:
    normalized = "".join(char.casefold() for char in text if char.isalnum())
    return normalized == normalized[::-1]


def by_two_pointers(text: str) -> bool:
    left, right = 0, len(text) - 1
    while left < right:
        while left < right and not text[left].isalnum():
            left += 1
        while left < right and not text[right].isalnum():
            right -= 1
        if text[left].casefold() != text[right].casefold():
            return False
        left += 1
        right -= 1
    return True


def by_deque(text: str) -> bool:
    chars = deque(char.casefold() for char in text if char.isalnum())
    while len(chars) > 1:
        if chars.popleft() != chars.pop():
            return False
    return True


class PalindromeTests(unittest.TestCase):
    def test_all_methods(self):
        cases = [
            ("A man, a plan, a canal: Panama", True),
            ("race a car", False),
            (" ", True),
            ("0P", False),
        ]
        for solve in (by_reverse, by_two_pointers, by_deque):
            for text, expected in cases:
                with self.subTest(solve=solve.__name__, text=text):
                    self.assertEqual(solve(text), expected)


if __name__ == "__main__":
    unittest.main()

Decision table

วิธี	เวลา	พื้นที่เสริม	จุดเด่น	เหมาะกับ
Normalize + reverse	O(n)	O(n)	สั้นและอ่านง่าย	โปรดักชันทั่วไป/input เล็ก
Two pointers	O(n)	O(1)	ไม่มีสำเนาทั้ง string	สัมภาษณ์และ input ใหญ่
Deque	O(n)	O(n)	แยกหัว/ท้ายชัด	iterator หรือการสอนโครงสร้างข้อมูล

Edge cases และขอบเขตจริง

ต้องเทสต์ string ว่าง, มีแต่ punctuation, ตัวเลข และคู่ที่ต่างกันใกล้กลาง สำหรับ LeetCode สัญญา input อยู่ในกรอบที่กำหนด แต่ Python isalnum() และ casefold() รองรับ Unicode กว้างกว่า ASCII และ case folding บางตัวอาจเปลี่ยนเป็นหลาย code point ถ้าระบบจริงต้องรองรับภาษาหลากหลาย ควร normalize Unicode เช่น NFC/NFKC ตามนโยบายก่อน และนิยามให้ชัดว่า accent หรือ grapheme cluster นับอย่างไร

Recap

• เริ่มจาก normalize-and-reverse เพื่อสื่อโจทย์ แล้วเสนอ two pointers เพื่อลดพื้นที่
• invariant ของ two pointers คือคู่ด้านนอกที่ตรวจแล้วตรงกันทั้งหมด
• deque เป็นทางเลือกที่ดีเชิงการสอน แต่ไม่ใช่ default สำหรับ string ใน memory
• ในโปรดักชันต้องนิยาม Unicode normalization เพิ่มจากสัญญา LeetCode ครับ