Python查詢分割回文串的方法數量程式

假設我們有一個字串 s，我們需要找到將字串分割成每個部分都是迴文串的方法的數量。

因此，如果輸入類似於 s = "xyyx"，則輸出將為 3，因為我們有如下分割方式：["x", "yy", "x"], ["x", "y", "y", "x"], ["xyyx"]。

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

  • n := s 的大小
  • table := 一個大小為 n + 1 的列表，並將其填充為 0
  • table[0] := 1
  • 對於 i 從 0 到 n，執行：
    • 對於 j 從 0 到 i - 1，執行：
      • sub := s[從索引 j 到 i]
      • 如果 sub 是迴文串，則：
        • table[i] := table[i] + table[j]
  • 返回 table 的最後一個元素

讓我們看看下面的實現來更好地理解。

示例

線上演示

class Solution:
   def solve(self, s):
      n = len(s)
      table = [1] + [0] * n
      for i in range(n + 1):
         for j in range(i):
            sub = s[j:i]
            if sub == sub[::-1]:
               table[i] += table[j]
      return table[-1]

ob = Solution()
s = "xyyx"
print(ob.solve(s))

輸入

"xyyx"

輸出

3

更新於：2020年11月26日

302 次檢視

開啟您的職業生涯

完成課程後獲得認證

開始學習
廣告