Chương trình tìm danh sách hiển thị khoảng cách gần nhất của ký tự c từ chỉ mục đó bằng Python

Giả sử chúng ta có một chuỗi s và một ký tự khác c, c phải có trong s, chúng ta phải tìm một danh sách có độ dài bằng độ dài của s, trong đó đối với mỗi chỉ số i giá trị của nó được đặt khoảng cách gần nhất của s [i] tới c.

Vì vậy, nếu đầu vào là s =​​"ppqppq" c ="q", thì đầu ra sẽ là [2, 1, 0, 1, 1, 0]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• j:=kích thước của s

• d:=[j - 1] * j

• x:=chỉ số của c trong s

• đối với tôi trong phạm vi từ 0 đến j - 1, thực hiện

  • nếu s [i] giống với c và i> x thì

    • x:=i, ind:=1

    • lặp qua phần sau, thực hiện

      • nếu d [x - ind]> ind, thì

        • d [x - ind]:=ind

      • nếu không,

        • đi ra từ vòng lặp

      • ind:=ind + 1

  • d [i]:=| x - i |

• trở lại d

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn

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]