โปรแกรมแยกสองสตริงเพื่อสร้าง palindrome โดยใช้ Python

สมมติว่าเรามีสองสตริง 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