สมมติว่าเรามีสองสตริง a และ b ที่มีความยาวเท่ากัน เราต้องเลือกดัชนีและแยกสตริงทั้งสองที่ดัชนีที่เลือก โดยแยก a เป็นสองสตริง:a_pref และ a_suff โดยที่ a =a_pref | a_suff และแยก b ออกเป็นสองสตริง:b_pref | b_suff (| เป็นตัวดำเนินการต่อ) โดยที่ b =b_pref + b_suff ตรวจสอบว่า a_pref + b_suff หรือ b_pref + a_suff สร้าง palindrome หรือไม่ (แยกใด ๆ อาจเป็นสตริงว่าง)
ดังนั้น ถ้าอินพุตเป็นเหมือน a ="pqrst" b ="turqp" ผลลัพธ์จะเป็น True เพราะเราสามารถแบ่ง a like ["pq", "rst"] และ b like ["tu", "rqp" ได้ ] ดังนั้นหากเราเข้าร่วม a_pref ด้วย b_suff เราจะได้รับ "pqrqp" ซึ่งเป็นพาลินโดรม
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
สำหรับแต่ละคู่ (x, y) จากรายการคู่ [(a, b), (b, a)] ทำ
-
ผม :=0, j :=ขนาด x - 1
-
ในขณะที่ x[i] เหมือนกับ y[j] และ i <ขนาดของ x และ j> 0 ทำ
-
ผม :=ผม + 1
-
เจ :=เจ - 1
-
-
midx :=สตริงย่อยของ x จากดัชนี i ถึง j
-
midy :=สตริงย่อยของ y จากดัชนี i ถึง j
-
ถ้า midx คือ palindrome หรือ midy คือ palindrome แล้ว
-
คืนค่า True
-
-
-
คืนค่าเท็จ
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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