โปรแกรมรับความยาวสูงสุดของสองสตริงที่กำหนดใน Python

สมมติว่าเรามีสองสตริง s และ t เราต้องสร้างสตริงที่เรียกว่า merge ด้วยวิธีต่อไปนี้ ในขณะที่ s หรือ t ว่างเปล่า ให้เลือกตัวเลือกใดตัวเลือกหนึ่งต่อไปนี้ -

• หาก s ไม่ว่าง ให้ผนวกอักขระตัวแรกใน s เพื่อรวมและลบออกจาก s

• หาก t ไม่ว่าง ให้ผนวกอักขระตัวแรกใน t เพื่อรวมและลบออกจาก t

ดังนั้นเราจึงต้องหาการรวมคำศัพท์ที่ใหญ่ที่สุดที่เราสามารถทำได้

ดังนั้น หากอินพุตเป็น s ="zxyxx" t ="yzxxx" เอาต์พุตจะเป็น zyzxyxxxx เพราะ

• เลือกจาก s:merge ="z", s ="xyxx", t ="yzxxx"

• เลือกจาก t:merge ="zy", s ="xyxx", t ="zxxx"

• เลือกจาก t:merge ="zyz", s ="xyxx", t ="xxx"

• เลือกจาก s:merge ="zyzx", s ="yxx", t ="xxx"

• เลือกจาก s:merge ="zyzxy", s ="xx", t ="xxx"

จากนั้นเพิ่ม 5 x ที่เหลือจาก s และ t เมื่อสิ้นสุดการรวม

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ตอบ :=สตริงว่าง

• idx1 :=0, idx2 :=0

• ในขณะที่ idx1 <ขนาดของ s และ idx2 <ขนาดของ t ทำ

  • ถ้า s[idx1]> t[idx2] หรือ (s[idx1] เหมือนกับ t[idx2] และสตริงย่อยของ s[จากดัชนี idx1 ถึง end]>=สตริงย่อยของ t[จากดัชนี idx2 ถึง end]) แล้ว

    • ans :=ans concatenate s[idx1]

    • idx1 :=idx1 + 1

  • มิฉะนั้นเมื่อ s[idx1]

    • ans :=ans concatenate t[idx2]

    • idx2 :=idx2 + 1

• ส่งคืน ans concatenate s[จากดัชนี idx1 ถึง end] concatenate t[จากดัชนี idx2 ถึง end]

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def solve(s, t):
   ans = ""
   idx1 = idx2 = 0
   while(idx1<len(s) and idx2<len(t)):
      if s[idx1]>t[idx2] or (s[idx1]==t[idx2] and s[idx1:]>=t[idx2:]):
         ans+=s[idx1]
         idx1+=1
      elif s[idx1]<t[idx2] or (s[idx1]==t[idx2] and s[idx1:]<=t[idx2:]):
         ans+=t[idx2]
         idx2+=1

   return ans+s[idx1:]+t[idx2:]

s = "zxyxx"
t = "yzxxx"
print(solve(s, t))

อินพุต

[7,4,5,3,8], [[0,2,2],[4,2,4],[2,13,100]]

ผลลัพธ์

zyzxyxxxxx