【Python】【LeetCode】【5.最长回文字符串】

文章目录

• • • 0.回文字符串
    • 1.原文题目
    • 2.解题思路
    • 3.Python代码

0.回文字符串

回文的意思是正着念和倒着念一样，如：上海自来水来自海上
人中柳如是
是如柳中人
楼望海海望楼
水连天天连水

1.原文题目

给定一个字符串 s，找到 s中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例1

输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。

示例2

输入: “cbbd”
输出: “bb”

2.解题思路

思路1
中心扩展：
把每个字母当成回文串的中心
这里要考虑两种情况，回文串的长度为奇数或者偶数情况。

思路2
把每个字母当成回文串的结束。

思路3
dp[i][j] 表示字符串从 j 到 i 是否是为回文串，即当 s[j] == s[i] 如果 dp[i-1][j+1] 也是回文串，那么字符串从 j 到 i 也是回文串，即 dp[i][j] 为真。

3.Python代码

# -*- coding: utf-8 -*- 
# @Time : 2019/5/17 12:48 
# @Author : ZXL 
# @Site :  
# @File : 5.最长回文字符串.py 
# @Software: PyCharm# 中心扩展法
class Solution1:def longestPalindrome(self, s):n = len(s)self.strhui = ''#函数里面定义一个函数def July(i, j):while i>=0 and j= 0 and even == even[::-1]:start = i - max_lenmax_len += 1elif i - max_len - 1 >= 0 and odd == odd[::-1]:start = i - max_len - 1max_len += 2return s[start:start + max_len]
print(Solution2().longestPalindrome('145541526'))

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！