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 次瀏覽

啟動您的職業生涯

透過完成課程獲得認證

開始
廣告