Longest Palindromic Substring

这题在leetcode上是第5题,在1.22首次尝试,然后不会,就拖到了现在…

原题链接

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

Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.

题意:求最长回文子串

字符串题经典中的经典

思路1.:与倒序字符串求最长公共子串?

还记得最开始接触字符串的时候,做的最多的题就是寻找两个字符串公共子串,那么看到本题第一想法就是把字符串和对应的逆序的字符串求最长子串,这样不就算出来回文子串了吗,然而直接这样求是个常见的错误,考虑这样一个字符串”abcdfcba”,逆序为”abcfdcba”,如果按上述思路求最长子串,可以求得回文串为”abc”,然而abc并不是回文串,这是因为倒序后的字符串与原字符相等部分的下标不同,如果加入下标检查则可以解决

思路2:中心扩展

根据回文的定义,一个回文子串一定是以字符串中间字符为基准中心对称的(偶数串中心为两个字符),那么我们就尝试以各个位置为中心向两边扩展,然后不断更新最长的回文串的长度和起始点

代码如下:

思路3:动态规划

状态转移方程

$P(i, j) = (P(i+1, j-1) \&\& S_i == S_j)$

代码如下

发表评论

电子邮件地址不会被公开。