ตรวจสอบว่าสตริงมีพาลินโดรมย่อยเฉพาะความยาวคี่หรือไม่ใน Python

ภาพรวม

บทความนี้ตรวจสอบว่าสตริง s มีพาลินโดรมย่อย (palindromic substring) ที่มีความยาวเป็นเลขคู่หรือไม่ ถ้ามี คืนค่า False (เพราะโจทย์ต้องการเฉพาะความยาวคี่)

ข้อสังเกตสำคัญ

พาลินโดรมความยาวคู่ที่สั้นที่สุดคือ 2 ตัวอักษรที่ติดกันเหมือนกัน (เช่น "aa", "bb") ดังนั้น ตรวจสอบแค่ว่ามีตัวอักษรติดกัน 2 ตัวที่เหมือนกันหรือไม่ ก็เพียงพอแล้ว

อัลกอริทึม

1. วนลูปตรวจสอบ s[i] == s[i+1] สำหรับทุก i
2. ถ้าพบ คืนค่า True (มีพาลินโดรมความยาวคู่)
3. ถ้าไม่พบ คืนค่า False (มีเฉพาะความยาวคี่)

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

def solve(string):
    for i in range(len(string) - 1):
        if string[i] == string[i + 1]:
            return True
    return False

s = "afternoon"
print(solve(s))  # True (มี "noon")

ผลลัพธ์

True

คำอธิบายเพิ่มเติม

โค้ดต้นฉบับมีลูป巢套 (nested loop) สร้างทุก substring ซึ่งเป็น O(n^2) แต่จริงๆ แล้ว ตรวจสอบแค่คู่ตัวอักษรติดกันก็เพียงพอ เพราะพาลินโดรมความยาวคู่ทุกตัวต้องมีคู่กลางที่เหมือนกัน