โปรแกรมแบ่งสตริงสองสตริงเพื่อสร้างพาลินโดรมใน Python

ปัญหา

สตริง a และ b ยาวเท่ากัน เลือกดัชนีหนึ่ง ตัดทั้งคู่ที่ดัชนีนั้น ได้ a_pref, a_suff และ b_pref, b_suff ตรวจสอบว่า a_pref + b_suff หรือ b_pref + a_suff เป็นพาลินโดรมหรือไม่ (อาจตัดว่างได้)

ตัวอย่าง

a="pqrst", b="turqp" → True (ตัด a:["pq","rst"], b:["tu","rqp"] → "pq"+"rqp" = "pqrqp" เป็นพาลินโดรม)

ขั้นตอนการแก้ปัญหา

1. สำหรับคู่ (x,y) ใน [(a,b), (b,a)]:
   • i:=0, j:=len(x)-1
   • بينما x[i]==y[j] and i0: i+=1; j-=1
   • midx := x[i:j+1], midy := y[i:j+1]
   • ถ้า midx==midx[::-1] หรือ midy==midy[::-1]: คืน True
2. คืน False

การนำไปใช้งาน (Python)

def solve(a, b):
    for x, y in [[a, b], [b, a]]:
        i, j = 0, len(x) - 1
        while x[i] == y[j] and i < len(x) and j > 0:
            i += 1
            j -= 1
        midx = x[i:j+1]
        midy = y[i:j+1]
        if (midx == midx[::-1] or midy == midy[::-1]):
            return True
    return False

a = "pqrst"
b = "turqp"
print(solve(a, b))

อินพุต

"pqrst", "turqp"

เอาต์พุต

True