โปรแกรมหาระยะห่างใกล้สุดถึงตัวอักษร c ในสตริง Python

ให้สตริง s และตัวอักษร c (มีใน s) สร้างลิสต์ความยาว len(s) ที่ i = ระยะห่างใกล้สุดจาก s[i] ถึง c

ตัวอย่าง: s="ppqppq", c="q" → [2,1,0,1,1,0]

ขั้นตอน (Two Pass / Single Pass)

1. หาตำแหน่ง c แรก x = s.index(c)
2. วน i ทุกตำแหน่ง:
   • เจอ c ใหม่ → อัปเดต x และ Propagate ระยะห่างย้อนกลับ
   • d[i] = abs(x-i)

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

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))  # Output: [2, 1, 0, 1, 1, 0]

อินพุต

"ppqppq", "q"

เอาต์พุต

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