最长回文子串

# 给你一个字符串 s,找到 s 中最长的回文子串。 
#
#
#
# 示例 1:
#
#
# 输入:s = "babad"
# 输出:"bab"
# 解释:"aba" 同样是符合题意的答案。

方法一:动态规划

# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def longestPalindrome(self, s: str) -> str:
        # https://www.jianshu.com/p/6f226c9180e2
        dp = [[False]*len(s) for _ in range(len(s))]    # 初始状态二维数组
        max_start, max_len = 0, 0
        for j in range(len(s)):                         # 右指针先走
            for i in range(j+1):                        # 左指针跟随
                if j-i < 2:
                    dp[i][j] = (s[i]==s[j])             # 最多相差一个元素
                else:
                    dp[i][j] = (s[i]==s[j]) and dp[i+1][j-1]        # 两端字符相等,中间也为回文子串
                # 记录索引值
                cur_len = j-i+1
                if dp[i][j] and max_len<cur_len:
                    max_len = cur_len
                    max_start = i
        return s[max_start:max_start+max_len]
# leetcode submit region end(Prohibit modification and deletion)

 

最长回文子串

上一篇:RabbitMQ_5、主题模式


下一篇:(十三)网络层--RIP协议报文格式