Tìm chuỗi giữa hai chuỗi theo thứ tự từ điển trong Python

Cho hai chuỗi S, T cùng độ dài. Tìm chuỗi cùng độ dài thỏa S < result < T theo thứ tự từ điển. Trả về -1 nếu không tồn tại.

Ví dụ: S="bbb", T="ddd" → "bbc".

Thuật toán

• Duyệt từ phải sang trái tìm ký tự đầu tiên khác 'z'
• Tăng ký tự đó lên 1, các ký tự sau đặt thành 'a'
• Nếu kết quả != T thì trả về, ngược lại -1

Ví dụ mã Python

def find_next(string):
    n = len(string)
    for i in range(n-1, -1, -1):
        if string[i] != 'z':
            k = ord(string[i])
            string[i] = chr(k + 1)
            return ''.join(string)
        string[i] = 'a'

S = "bbb"
T = "ddd"
S = list(S)
res = find_next(S)
if res != T:
    print(res)
else:
    print(-1)

Đầu vào

"bbb", "ddd"

Đầu ra

bbc