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

สมมติว่ามีสตริง s และ t เราต้องสร้างสตริง merge ดังนี้: כל עוד s หรือ t ไม่ว่าง ให้เลือกหนึ่งในสองทางเลือก:

• ถ้า s ไม่ว่าง ให้นำตัวอักษรแรกของ s ต่อท้าย merge และลบออกจาก s
• ถ้า t ไม่ว่าง ให้นำตัวอักษรแรกของ t ต่อท้าย merge และลบออกจาก t

หา merge ที่มีลำดับเล็กซิโครกราฟิก (lexicographically) มากที่สุด

ตัวอย่าง: s = "zxyxx", t = "yzxxx" ผลลัพธ์คือ zyzxyxxxxx

วิธีแก้ปัญหา

1. ans := สตริงว่าง
2. idx1 := 0, idx2 := 0
3. วนลูป while idx1 < len(s) and idx2 < len(t):
   • ถ้า s[idx1] > t[idx2] หรือ (s[idx1] == t[idx2] และ s[idx1:] >= t[idx2:]):
     • ans += s[idx1]
     • idx1 += 1
   • มิฉะนั้น:
     • ans += t[idx2]
     • idx2 += 1
4. คืนค่า ans + s[idx1:] + t[idx2:]

ตัวอย่างโค้ด

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))

อินพุต

"zxyxx", "yzxxx"

เอาต์พุต

zyzxyxxxxx