โปรแกรมหาการรวมสตริงสองสตริงแบบเล็กซิโคกราฟิกมากที่สุดใน Python

ปัญหา

มีสตริง s และ t ต้องสร้างสตริง merge โดยเลือกตัวอักษรแรกของ s หรือ t ต่อท้าย merge จนกว่าทั้งสองจะว่างเปล่า ต้องการ merge ที่ใหญ่ที่สุดในแบบเล็กซิโคกราฟิก

ตัวอย่าง

s = "zxyxx", t = "yzxxx" → ผลลัพธ์ "zyzxyxxxxx"

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

1. a := 0, b := 0, merge := ""
2. W1 := len(s), W2 := len(t)
3. بينما a < W1 and b < W2:
   • ถ้า s[a:] > t[b:]: merge += s[a]; a += 1
   • มิฉะนั้น: merge += t[b]; b += 1
4. คืน merge + s[a:] + t[b:]

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

def solve(s, t):
    a = b = 0
    merge = ""
    W1 = len(s)
    W2 = len(t)
    while a < W1 and b < W2:
        if s[a:] > t[b:]:
            merge += s[a]
            a += 1
        else:
            merge += t[b]
            b += 1
    return merge + s[a:] + t[b:]

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

อินพุต

"zxyxx", "yzxxx"

เอาต์พุต

zyzxyxxxxx