โปรแกรมสร้าง Lexicographically Minimal String จากสองสตริงใน Python

ให้สตริงสองตัว สร้างสตริง Minimal โดยเปรียบเทียบตัวแรกของทั้งสอง เลือกตัวน้อยกว่า (เท่ากันเลือกสตริงแรก) ทำซ้ำจนหมด

ตัวอย่าง: input1='TUTORIALS', input2='POINT' → 'POINTTUTORIALS'

ขั้นตอน (Greedy Merge)

1. เติม Sentinel 'z' ท้ายทั้งสอง
2. Two Pointer temp1, temp2
3. เปรียบเทียบ Suffix input1[temp1:] vs input2[temp2:]
4. เลือกตัวน้อยกว่า ขยับ Pointer นั้น
5. ตัด Sentinel ท้าย

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

def solve(input_1, input_2):
    input_1 += "z"
    input_2 += "z"
    temp_1 = 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'))  # Output: POINTTUTORIALS

อินพุต

'TUTORIALS', 'POINT'

เอาต์พุต

POINTTUTORIALS