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]

更新于: 2021年10月11日

382 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告