Python程序：查找通过修剪字符串可以生成的回文数量

假设我们有一个字符串s，我们需要找到通过修剪s的左右两侧可以获得回文的方式数量。

例如，如果输入是s = "momo"，则输出将是6，因为您可以得到["mom", "omo", "mo", "om", "o", "m"]。

为了解决这个问题，我们将遵循以下步骤：

  • 定义一个函数expand()。它将接收i、j、s。

  • c := 0

  • 当i >= 0 且 j < s的长度 且 s[i] 等于 s[j] 时，执行以下操作：

    • i := i − 1, j := j + 1

    • c := c + 1

  • 返回c

  • 在主方法中，执行以下操作：

  • c := 0

  • 对于范围0到s长度的i，执行以下操作：

    • c := c + expand(i, i, s)

    • c := c + expand(i, i + 1, s)

  • 返回c

让我们看下面的实现来更好地理解：

示例

在线演示

def expand(i, j, s):
   c = 0
   while i >= 0 and j < len(s) and s[i] == s[j]:
      i −= 1
      j += 1
      c += 1
   return c
class Solution:
   def solve(self, s):
      c = 0
      for i in range(len(s)):
         c += expand(i, i, s)
         c += expand(i, i + 1, s)
      return c
ob = Solution()
s = "momo"
print(ob.solve(s))

输入

"momo"

输出

6

更新于：2020年10月21日

182 次浏览

启动您的职业生涯

通过完成课程获得认证

开始
广告