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 次查看

开启您的职业生涯

完成课程后获得认证

开始学习
广告