Chương trình tạo chuỗi nhỏ nhất theo thứ tự từ điển từ hai chuỗi trong Python

Cho hai chuỗi. Tạo chuỗi nhỏ nhất theo thứ tự từ điển bằng cách lần lượt so sánh ký tự đầu của hai chuỗi, lấy ký tự nhỏ hơn (nếu bằng nhau lấy từ chuỗi đầu). Lặp cho đến khi cả hai rỗng.

Ví dụ: , → kết quả .

Quá trình: so sánh 'T' vs 'P' → lấy 'P', tiếp 'T' vs 'O' → lấy 'O', ... cuối cùng chuỗi 2 hết, nối toàn bộ chuỗi 1 còn lại.

Thuật toán giải quyết (Hai con trỏ + So sánh chuỗi con)

1. Thêm ký tự 'z' (lớn nhất) vào cuối cả hai chuỗi làm sentinel
2. Hai con trỏ , kết quả
3. Khi cả hai con trỏ chưa hết:
   • So sánh chuỗi con từ con trỏ:
   • Lấy ký tự từ chuỗi nhỏ hơn, tiến con trỏ đó
4. Loại bỏ sentinel 'z' cuối
5. Nối phần còn lại của chuỗi nào chưa hết

Ví dụ minh họa

def solve(input_1, input_2):
    input_1 += "z"
    input_2 += "z"
    temp_1 = 0
    temp_2 = 0
    res_str = ""
    while temp_1 < len(input_1) and temp_2 < len(input_2):
        if input_1[temp_1:] < input_2[temp_2:]:
            res_str += input_1[temp_1]
            temp_1 += 1
        else:
            res_str += input_2[temp_2]
            temp_2 += 1
    res_str = res_str[:-1]
    if temp_1 < len(input_1):
        res_str += input_1[temp_1:-1]
    if temp_2 < len(input_2):
        res_str += input_2[temp_2:-1]
    return res_str

print(solve('TUTORIALS', 'POINT'))

Đầu vào

'TUTORIALS', 'POINT'

Đầu ra

POINTTUTORIALS