Chương trình tạo số nhỏ nhất không có hai chữ số liền kề giống nhau Python

Cho chuỗi s chứa '1','2','3','?'. Thay '?' bằng '1','2' hoặc '3' để tạo số nhỏ nhất không có hai chữ số liền kề giống nhau.

Ví dụ: → 21231.

Giải thuật (Tham lam trái sang phải)

1. Duyệt từng ký tự từ trái sang phải
2. Nếu gặp '?': chọn chữ số nhỏ nhất ('1' → '2' → '3') khác với chữ số bên trái (đã xác định) và bên phải (nếu đã biết, chưa xử lý thì bỏ qua)
3. Xử lý riêng vị trí đầu và cuối

Ví dụ triển khai

def solve(s):
    i = 0
    s = list(s)
    if len(s) < 2:
        if s[0] == "?":
            return "1"
    while i < len(s):
        if s[i] == "?":
            if i == 0:
                s[i] = "1" if s[i+1] != "1" else "2"
            elif i > 0 and i <= len(s) - 2:
                if s[i-1] == "1":
                    s[i] = "3" if s[i+1] == "2" else "2"
                elif s[i-1] == "2":
                    s[i] = "3" if s[i+1] == "1" else "1"
                else:  # s[i-1] == "3"
                    s[i] = "2" if s[i+1] == "1" else "1"
            else:  # i == len(s)-1
                s[i] = "1" if s[i-1] != "1" else "2"
        i += 1
    return "".join(s)

print(solve("2??3?"))

Đầu vào

"2??3?"

Đầu ra

21231