Chương trình tìm chuỗi hợp nhất lớn nhất theo thứ tự từ điển của hai chuỗi trong Python

Cho hai chuỗi s và t. Xây dựng chuỗi merge bằng cách lặp lại: lấy ký tự đầu của s hoặc t (nếu không rỗng) nối vào merge và xóa khỏi chuỗi gốc. Tìm merge lớn nhất theo thứ tự từ điển (lexicographically largest).

Ví dụ: s = "zxyxx", t = "yzxxx" → "zyzxyxxxxx".

Giải thuật (Tham lam)

1. Con trỏ a = 0 (vị trí trong s), b = 0 (vị trí trong t).
2. Trong khi a < len(s) và b < len(t):
   • So sánh phần còn lại: s[a:] vs t[b:].
   • Nếu s[a:] > t[b:]: nối s[a], a += 1.
   • Ngược lại: nối t[b], b += 1.
3. Nối phần còn lại của s và t.

Ví dụ minh họa

def solve(s, t):
    a = b = 0
    merge = ""
    W1, W2 = len(s), 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))

Đầu vào

"zxyxx", "yzxxx"

Đầu ra

zyzxyxxxxx