[LeetCode] 5.Longest Palindromic Substring

本文主要是介绍[LeetCode] 5.Longest Palindromic Substring，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目内容

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

https://leetcode-cn.com/problems/longest-palindromic-substring/

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:Input: "cbbd"
Output: "bb"

 

---

题目思路

回文子串分为两种类型。第一种是长度为奇数的字符串，第二种是长度为偶数的字符串。

程序从第一个字符遍历到最后一个字符，采用动态规划的方式，计算到第i次为止，已知最长的回文字符串是什么情况。因为只需要比较最大的，所以每次和比最大长度多1或者多2的进行比较即可。在比较的时候，注意是先把+2的那个串放前面，如果符合+2的串，就不需要再比较+1的串了。（而且+2的串和+1的串是互斥的）每次遍历时分别判断奇数长度的字符串和偶数长度的字符串是否是回文串。

---

程序代码

class Solution(object):def longestPalindrome(self, s):""":type s: str:rtype: str"""length = len(s)max_length,start = 0,0for i in range(length):left1,left2=i - max_length-1,i - max_lengthif left1 >= 0 and s[left1: i+1] == s[left1: i+1][::-1]:start = left1max_length += 2#continueelif left2 >= 0 and s[left2: i+1] == s[left2: i+1][::-1]:start = left2max_length += 1return s[start: start + max_length]

 

这篇关于[LeetCode] 5.Longest Palindromic Substring的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---