给定一个字符串,输出所有长度至少为2的回文子串。 回文子串即从左往右输出和从右往左输出结果是一样的字符串,比如:abba,cccdeedccc都是回文字符串。
时间: 2023-05-04 20:01:52 浏览: 466
题目要求输入一个字符串,输出所有长度至少为2的回文子串。回文子串是指从左往右和从右往左读都一样的字符串。
我们可以使用两个指针i,j去扫描字符串,判断从i到j的子串是否为回文子串。具体做法是,如果s[i]==s[j],我们就继续往中间扩展,也就是i往左移动一格,j往右移动一格,直到i>=0或者j>=len(s),或者s[i]!=s[j]为止。如果中途发现s[i]!=s[j],那么(i+1,j-1)不可能为回文子串,我们直接跳出循环;否则,(i,j)就是一个回文子串,我们将它append到结果列表中即可。
代码如下:
def palindrome(s):
res = []
n = len(s)
for i in range(n):
for j in range(i+1, n):
if s[i] == s[j]:
left, right = i, j
while left < right and s[left] == s[right]:
left += 1
right -= 1
if left >= right:
res.append(s[i:j+1])
return res
下面是一些测试样例:
assert palindrome("abba") == ["a", "b", "bb", "abba"]
assert palindrome("abcbad") == ["a", "b", "c", "b", "d", "bccb", "bcb"]
assert palindrome("abbccddeeff") == ["a", "b", "bb", "bccb", "cc", "dd", "ee", "ff", "ddeedd", "eeffee"]
注意,上面的测试样例并不是唯一的正确答案,因为回文子串的顺序可能不同。比如"abbccddeeff"可以输出ddeedd和eeffee,也可以输出"ee", "ff", "dd", "ddeedd", "eeffee",都是正确的答案。
阅读全文