最长回文子串
文章目录
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
暴力法
将选出所有子字符串可能的开始和结束位置，并检验它是不是回文。
时间复杂度：O(n^2)，往往利用python的切片可以很好的缩减复杂度
如果不用切片，还需要遍历一次子字符串，时间复杂度就是O(^3)
空间复杂度：O(1)
ps: 官方给出的时间复杂度是没有考虑python切片的功能
python
def force(self, s: str) -> str:
if s==s[::-1]:
return s
max_len = 1
res = s[0]
for i in range(len(s) - 1):
for j in range(i + 1, len(s)):
if j - i + 1 > max_len and s[i:j+1] == s[i:j+1][::-1]:
max_len = j - i + 1
res = s[i:j + 1]
return res
动态规划 - 中心扩散法
时间复杂度 O(N^2)
空间复杂度⾄少要 O(N^2) 来存储 DP table。（推荐双指针，只需O(1)空间）
:
为了改进暴力法，我们首先观察如何避免在验证回文时进行不必要的重复计算。考虑“ababa” 一定是回文，因为它的左首字母和右尾字母是相同的。
我们给出 P(i,j) 的定义如下：
如果子串S_i和S_j是回文字符串则P(i,j)为ture
其他情况，P(i,j)为false
因此 P(i,j)=(P(i+1,j−1) and S_i==S_j)
基本示例如下：
P(i, i) = true
P(i, i+1) = ( S_i == S_{i+1} )
这产生了一个直观的动态规划解法，我们首先初始化一字母和二字母的回文，然后找到所有三字母回文，并依此类推…
#中心扩散法Spread From Center
def spread(self, s, left, right):
"""
left = right 的时候，此时回文中心是一条线，回文串的长度是奇数
right = left + 1 的时候，此时回文中心是任意一个字符，回文串的长度是偶数
"""
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return s[left + 1:right]
# 动态规划法-中心扩散法Spread From Center
def spread_from_center(self, s:str) -> str:
if s==s[::-1]:
return s
res = s[:1]
for i in range(len(s)):
palindrome_odd= self.spread(s,i, i)
palindrome_even= self.spread(s,i, i + 1)
# 当前找到的最长回文子串
res = max(palindrome_odd,palindrome_even,res,key=len)
return res
双指针 - 中心扩散
回⽂串就是正着读和反着读都⼀样的字符串
回⽂串的⻓度可能是奇数也可能是偶数
寻找回⽂串的问题核⼼思想是：从中间开始向两边扩散来判断回⽂串，主串从头到尾：找到以 s[i] 为中⼼的回⽂串，假设s[i]为子串中心，向两边扩展进行判断
for 0 <= i < len(s):
找到以 s[i] 为中⼼的回⽂串
更新答案
但是呢，回⽂串的⻓度可能是奇数也可能是偶数，如果是abba 这种情况，没有⼀个中⼼字符，上⾯的算法就没辙了。所以我们可以修改⼀下：
for 0 <= i < len(s):
找到以 s[i] 为中⼼的回⽂串
找到以 s[i] 和 s[i+1] 为中⼼的回⽂串
更新答案
实现⼀个函数来寻找最⻓回⽂串
p(s, i, i)：找到以 s[i] 为中⼼的回⽂串
c a b c b a a
-- (l/r)
----l --- r (l--,r++)：while(l >= 0 && r < s.size()&& s[l] == s[r]
--l-------- r
l-------------r 此时跳出while，l+1是回文子串的开始，r-1是回文子串的结尾，回文子串长度是此时两指针间长度-2，(r-l+1)-2
所以回文子串是s.substr(l+1, r-l-1)
p(s, i, i+1)：找到以 s[i],s[i+1] 为中⼼的回⽂串
c a b b a d
-- l r
--l --- r (l--,r++)：while(l >= 0 && r < s.size()&& s[l] == s[r]
l---------r 此时跳出while，l+1是回文子串的开始，r-1是回文子串的结尾，回文子串长度是此时两指针间长度-2，(r-l+1)-2
所以回文子串是s.substr(l+1, r-l-1)
string palindrome(string& s, int l, int r) {
// 防⽌索引越界
while (l >= 0 && r < s.size()&& s[l] == s[r]) {
// 向两边展开
l--; r++;
}
// 返回以 s[l] 和 s[r] 为中⼼的最⻓回⽂串
return s.substr(l + 1, r - l - 1);
}
传⼊两个指针 l 和 r 实现可以同时处理回⽂串⻓度为奇数和偶数的情况：
for 0 <= i < len(s):
# 找到以 s[i] 为中⼼的回⽂串
palindrome(s, i, i)
# 找到以 s[i] 和 s[i+1] 为中⼼的回⽂串
palindrome(s, i, i + 1)
更新答案
longestPalindrome 的完整代码：
时间复杂度 O(N^2)，空间复杂度 O(1)
string longestPalindrome(string s) {
string res;
for (int i = 0; i < s.size(); i++) {
// 以 s[i] 为中⼼的最⻓回⽂⼦串
string s1 = palindrome(s, i, i);
// 以 s[i] 和 s[i+1] 为中⼼的最⻓回⽂⼦串
string s2 = palindrome(s, i, i + 1);
// res = longest(res, s1, s2)
res = res.size() > s1.size() ? res : s1;
res = res.size() > s2.size() ? res : s2;
}
return res;
}
python解答
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
def palindrome(s, l, r):
while l>=0 and r<len(s) and s[l] == s[r]:
l=l-1
r=r+1
return s[l+1: r]# 切片，需要首尾即可
res=''
for i in range(len(s)):
s1 = palindrome(s, i, i)
s2 = palindrome(s, i, i+1)
res = res if len(res) > len(s1) else s1
res = res if len(res) > len(s2) else s2
return res
注
- 题目中“你可以假设 s 的最大长度为 1000”：说明时间复杂度不能超过O(n^2)，1千的平方正好是1百万
1百万规则：输入规模代入时间复杂度公式，超过1百万很可能超时 - 判断一个字符串是否回文
a b c b a
0 1 - - - 只判断 0到n/2处的字符即可：for i in range(n/2)
i-------n-i-1 （if s[i] != s[n-i-1]: return false）
# entire string
def isPalindrome(s):
n = len(s)
for i in range(n/2):
if s[i] != s[n-i-1]: return false
return true
- 判断一个str的子串是否回文
a b c b a (b b)
l - -- r 从子串两端开始
l - r
# substring s[l~r]
def isPalindrome(s,l,r):
while l<r:
if s[l] != s[r]: return false
l++
r--
return true
Python逻辑运算符 ： and or not
结尾不用分号；
在python中是没有自增和自减的，但在python中存在 i = i + 1和 i = i -1 的情况。
Python代码块使用缩进对齐表示代码逻辑，而不是使用大括号
没有三元运算符： res = res if len(res) > len(s1) else s1
Python中字符串切片：字符串[开始索引：结束索引：步长]，切取字符串为开始索引到结束索引-1内的字符串，切片需要首尾即可
num_str_1 = num_str[2:6] # 截取2 - 5位置的字符
python中创建变量不需要声明，变量赋值不需要类型声明。