如何用自己电脑做网站服务器,网络建设的重要性,如何制作聊天软件,给公司制作网站吗题目描述
给你一个字符串 s#xff0c;找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同#xff0c;则该字符串称为回文字符串。
示例 1#xff1a;
输入#xff1a;s babad
输出#xff1a;bab
解释#xff1a;aba找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同则该字符串称为回文字符串。
示例 1
输入s babad
输出bab
解释aba 同样是符合题意的答案。示例 2
输入s cbbd
输出bb思路 【参考官方题解动态规划】
class Solution(object):def longestPalindrome(self, s)::type s: str:rtype: strn len(s)if n 2:return smax_len 1 # 记录最长的回文字串的长度begin 0 # 记录开始位置到时候一加就可以找出字符串# ababadp [[False] * n for _ in range(n)] # 用于记录是否是回文字串for i in range(n):dp[i][i] True # 自己到自己肯定是for L in range(2, n 1): # 这个是间隔从2开始for i in range(n):j i L - 1 # -1是从相邻的两个位置比较【01】【12】【23】if j n: # 超出字串串本身的长度步子太大了就跳出去breakif s[i] ! s[j]: # 如果不相等返回falsedp[i][j] Falseelse: # 如果相等有两种情况if j - i 3: # 如果间隔中就一个或者批次挨着dp[i][j] True # 直接返回true就行else: # 如果间隔中有2个及以上的字符dp[i][j] dp[i 1][j - 1] # 就需要看dp[i1][j-1]if dp[i][j] and j - i 1 max_len: # 如果是回文字串并且长度大于最大长度max_len j - i 1 # 则进行更新begin ireturn s[begin:begin max_len] if __name__ __main__:s Solution()print(s.longestPalindrome(ababa))
