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

Mô tả bài toán

Cho hai chuỗi s và t. Chúng ta tạo chuỗi merge bằng cách lặp lại: nếu s không rỗng, lấy ký tự đầu tiên của s thêm vào merge và xóa nó khỏi s; nếu t không rỗng, lấy ký tự đầu tiên của t thêm vào merge và xóa nó khỏi t. Hãy tìm chuỗi merge lớn nhất theo thứ tự từ điển (lexicographically largest).

Ví dụ

Nếu đầu vào là s = "zxyxx", t = "yzxxx", thì đầu ra sẽ là "zyzxyxxxxx".

Giải thuật

1. Khởi tạo ans = "", idx1 = 0, idx2 = 0.
2. Trong khi idx1 < len(s) và idx2 < len(t):
   • Nếu s[idx1] > t[idx2] hoặc (s[idx1] == t[idx2] và s[idx1:] >= t[idx2:]):
     • Thêm s[idx1] vào ans, tăng idx1.
   • Ngược lại:
     • Thêm t[idx2] vào ans, tăng idx2.
3. Trả về ans + s[idx1:] + t[idx2:].

Triển khai Python

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
        else:
            ans += t[idx2]
            idx2 += 1
    return ans + s[idx1:] + t[idx2:]

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

Đầu vào

"zxyxx", "yzxxx"

Đầu ra

zyzxyxxxxx