Chương trình tìm khoảng cách gần nhất đến ký tự c cho mỗi vị trí trong chuỗi Python

Cho chuỗi s và ký tự c (chắc chắn có trong s). Tạo mảng cùng độ dài s mà tại chỉ số i giá trị là khoảng cách nhỏ nhất từ đến ký tự c bất kỳ.

Ví dụ: , → kết quả [2, 1, 0, 1, 1, 0].

Thuật toán giải quyết (Hai lần quét / Two-pass)

1. Khởi tạo d mảng độ dài j giá trị j-1
2. Tìm chỉ số đầu tiên của c: x = s.index(c)
3. Duyệt i từ 0 đến j-1:
   • Nếu gặp c mới (i > x): cập nhật x = i, lan truyền ngược cập nhật khoảng cách cho các vị trí trước
   • d[i] = abs(x - i)
4. Trả về d

Lưu ý: Cách tiếp cận chuẩn thường dùng 2 lần quét (trái→phải và phải→trái) để đơn giản hơn.

Ví dụ minh họa

def solve(s, c):
    j = len(s)
    d = [j - 1] * j
    x = s.index(c)
    for i in range(j):
        if s[i] == c and i > x:
            x = i
            ind = 1
            while True:
                if d[x - ind] > ind:
                    d[x - ind] = ind
                else:
                    break
                ind += 1
        d[i] = abs(x - i)
    return d

s = "ppqppq"
c = "q"
print(solve(s, c))

Đầu vào

"ppqppq", "q"

Đầu ra

[2, 1, 0, 1, 1, 0]