最长回文子串
程序员文章站
2022-05-29 07:52:01
...
其实最简单的就是暴力法,但是python3会超时(也不知道出题人搞那么多a干啥)
学习了中心扩展的方法,易懂,但我觉得不太容易操作(对于我这个菜鸟来说),当然,得知palindrome用法时就大概懂了,原来大部分代码时在限制条件,而回文确是一步到位。
class Solution:
def longestPalindrome(self, s: str) -> str:
size = len(s)
if size < 2:
return s
max_len = 1
res = s[0]
for i in range(size):
palindrome_os, os_len = self.zhongxin(s, size, i, i)
palindrome_js, js_len = self.zhongxin(s, size, i, i + 1)
cur_max_sub = palindrome_os if os_len >= js_len else palindrome_js
if len(cur_max_sub) > max_len:
max_len = len(cur_max_sub)
res = cur_max_sub
return res
def zhongxin(self, s, size, left, right):#构造函数
i = left
j = right
while i >= 0 and j < size and s[i] == s[j]:
j += 1
i -= 1
return s[i + 1:j], j - i - 1