5. 最长回文子串
思路
首先判断字符串是否是回文,是则直接返回,不是则遍历:
从第一个字符开始遍历,判断对应字符串是否是回文且是不是最大长度
时间复杂度:O(N^3)
动态规划解法:
状态初始化为False
dp[i][j]回文:s[i]=s[j]且[i-1:j-1]也为回文
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
# if s==s[::-1]:
# return s
# #超限
# t=''
# n=''
# for i in range(len(s)):
# for j in range(i+1,len(s)+1):
# t=s[i:j]
# if t==t[::-1] and len(n)<len(t):
# n=t
# return n
'''
动态规划来解:dp[i][j]与dp[i+1][j-1]有关 [i:j]为回文,则s[i]=s[j]且[i-1:j-1]也为回文
j-i<=1情况: aba ab 代表字符串长度为奇、偶情况
'''
n=''
dp=[[False]*len(s) for _ in range(len(s))]
for i in range(len(s)-1,-1,-1):
for j in range(len(s)-1,i-1,-1):
if s[i]==s[j]:
if j-i<=1:
dp[i][j]=True
elif dp[i+1][j-1]:
dp[i][j]=True
if dp[i][j] and (j+1-i)>len(n):
n=s[i:j+1]
return n
原文地址:https://blog.csdn.net/huanxianxianshi/article/details/142764539
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!