โปรแกรมค้นหารายการที่แสดงระยะทางที่ใกล้ที่สุดของอักขระ c จากดัชนีนั้นใน Python

สมมติว่าเรามีสตริง s และอักขระอื่น c, c ต้องมีอยู่ใน s เราต้องค้นหารายการที่มีความยาวเท่ากับความยาวของ s โดยที่ดัชนีแต่ละตัว i ค่าของมันถูกตั้งค่าระยะทางที่ใกล้ที่สุดของ s[i] เป็น ค.

ดังนั้น หากอินพุตเป็น s ="ppqppq" c ="q" ผลลัพธ์จะเป็น [2, 1, 0, 1, 1, 0]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• j :=ขนาดของ s

• d :=[j - 1] * j

• x :=ดัชนีของ c ใน s

• สำหรับฉันอยู่ในช่วง 0 ถึง j - 1 ทำ

  • ถ้า s[i] เหมือนกับ c และ i> x แล้ว

    • x :=i, ind :=1

    • วนซ้ำต่อไปนี้ทำ

      • ถ้า d[x - ind]> ind แล้ว

        • d[x - ind] :=ind

      • มิฉะนั้น

        • ออกจากวง

      • ind :=ind + 1

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

• กลับ d

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น

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))

อินพุต

"ppqppq", "q"

ผลลัพธ์

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