Python 中查找给定字符串的所有回文子字符串 - 方法二

假设我们有一个字符串；我们需要从该字符串中找到所有回文子字符串。这里 aa 和 aa 被认为是两个子字符串，而不是一个。

因此，如果输入类似于 redivider，则输出将为 ['r', 'e', 'd', 'i', 'v', 'ivi', 'divid', 'edivide', 'redivider', 'i', 'd', 'e', 'r']

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

  • v := 一个新的列表
  • pos := 0.0
  • 当 pos < s 的大小 时，执行
    • rad := pos - (pos 的整数部分)
    • 当 (pos + rad) < s 的大小 且 (pos - rad) >= 0 且 (s[pos - rad 的整数部分] 等于 s[pos + rad 的整数部分]) 时，执行
      • 将 s[从索引 pos - rad 的整数部分 到 pos + rad + 1 的整数部分] 插入到 v 的末尾
      • rad := rad + 1
    • pos := pos + 0.5
  • 返回 v

示例代码

让我们看看以下实现，以便更好地理解 -

 实时演示

def get_all_pal_sub(s):
   v = []
   pos = 0.0
   while pos < len(s):
      rad = pos - int(pos)
      while ((pos + rad) < len(s) and (pos - rad) >= 0 and (s[int(pos - rad)] == s[int(pos + rad)])):
         v.append(s[int(pos - rad): int(pos + rad + 1)])
         rad += 1
      pos += 0.5
   return v
v = get_all_pal_sub("redivider")
print(len(v))
print(v)

输入

"redivider"

输出

13 ['r', 'e', 'd', 'i', 'v', 'ivi', 'divid', 'edivide', 'redivider', 'i', 'd', 'e', 'r']

更新于: 2020年8月28日

88 次浏览

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告