Python程式：查詢字元c在字串中每個索引處最近距離的列表

假設我們有一個字串s和另一個字元c，c必須出現在s中，我們需要找到一個列表，其長度與s的長度相同，並且對於每個索引i，其值設定為s[i]到c的最短距離。

因此，如果輸入類似於s = "ppqppq" c = "q"，則輸出將為[2, 1, 0, 1, 1, 0]

為了解決這個問題，我們將遵循以下步驟：

• j := s的長度

• d := [j - 1] * j

• x := c在s中的索引

• 對於範圍從0到j - 1的i，執行以下操作：

  • 如果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]

Arnab Chakraborty

更新於: 2021年10月11日

382 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習