【LeetCode】修炼之路-0005-Longest Palindromic Substring【python】
题目
Given a string s, return the longest palindromic substring in s.
Example 1:
Input: s = “babad”
Output: “bab”
Explanation: “aba” is also a valid answer.
Example 2:
Input: s = “cbbd”
Output: “bb”
前言
首先，题目我们就看不懂 ，上网冲浪一下发现， longest palindromic substring是最长回文字串的意思，就是从左右对称的一个数组。
思路1：暴力
我们把所有可能都罗列出来，然后判断每个是不是回文字符串。
判断是不是回文字符串
回文字符串怎么判断呢，我们可以比头尾，比如
对于偶数的字符串s=‘’abba’，长度len(s)是4，
我们可以从start=0,end=3开始
case1 偶数长度的字符串
对于字符串 “abba”：
√ 步骤 1 (start = 0, end = 3):
| a | b | b | a | |
|---|---|---|---|---|
| 下标 | 0 | 1 | 2 | 3 |
| 指针 | start | end |
√ 步骤 2 (start = 1, end = 2):
| a | b | b | a | |
|---|---|---|---|---|
| 下标 | 0 | 1 | 2 | 3 |
| 指针 | start | end |
X 步骤 3 (start = 2, end = 1):
| a | b | b | a | |
|---|---|---|---|---|
| 下标 | 0 | 1 | 2 | 3 |
| 指针 | end | start |
我们通过步骤1和步骤2去观察我们需要的循环条件，然后看我们的循环条件怎么写
1.我们需要的整个过程start=0,1 end是3,2，start始终处在小于end的状态下，所以我们的循环条件可以写start＜end：
参考代码：
def is_palindrome(s):
start = 0
end = len(s) - 1
while start < end:
if s[start] != s[end]:
return False # 不符合就终止
start += 1 # start往后递进
end -= 1 # end往前递进
return True
2.因为是对称的，所以我们的start一定是走到一半就停止，即：start＜ len(s)//2 也可以做为我们的循环条件
def is_palindrome(s):
start = 0
end = len(s) - 1
while start < len(s) // 2:
if s[start] != s[end]:
return False # 不符合就终止
start += 1 # start往后递进
end -= 1 # end往前递进
return True
我们还可以怎么写呢，while循环是从状态的思路去考虑循环的，实际上，第二种思路，我们知道我们要循环多少次，通过次数去写循环，我们还可以用 for i in rang() 这种写法
def is_palindrome(s):
length = len(s)
end = length - 1
for start in range(length // 2):
if s[start] != s[end]:
return False # 不符合就终止
end -= 1 # end往前递进
return True
精简版本：
def is_palindrome(s):
length = len(s)
for i in range(length // 2):
if s[i] != s[length - 1 - i]:
return False
return True
然后我们得到偶数情况下的代码了，我们考虑一下奇数情况下会发生什么。
case2 对于奇数长度的字符串
对于字符串 “abcba”：
步骤 1 (start = 0, end = 4):
| a | b | c | b | a | |
|---|---|---|---|---|---|
| 下标 | 0 | 1 | 2 | 3 | 4 |
| 指针 | start | end |
步骤 2 (start = 1, end = 3):
| a | b | c | b | a | |
|---|---|---|---|---|---|
| 下标 | 0 | 1 | 2 | 3 | 4 |
| 指针 | start | end |
步骤 3 (start = 2, end = 2):
| a | b | c | b | a | |
|---|---|---|---|---|---|
| 下标 | 0 | 1 | 2 | 3 | 4 |
| 指针 | start/end |
看上去我们似乎需要修改我们的代码，因为这里的循环条件似乎变成了start ≤ end，有些新东方的学员可能就非常有实干精神去改代码了，然后说，看我做了奇偶条件判断，我真是逻辑严密得滴水不漏啊！
为了帮助大家建立更好的思维路径，我们进一步思考一下这个问题，对于判断回文字符串，我们是不是还可以用递归的思想来看这个问题。我们可以降低这个问题的规模，然后一步一步解决吗？
让我们从空字符串，单个字符，两个字符，三个字符依次来思考：
我们 让 P(n) 表示判断长度为 n 的字符串是否为回文字符串的问题。（特别地让 *P(2) 表示判断字符串首尾字符是否一致。）
*P(2) = (s[0] == s[n-1]) （判断首尾字符是否相同）
基本情况：
P(0) = true （空字符串是回文）
P(1) = true （单个字符总是回文）
递归关系：
对于 n ≥ 2：
P(2) = *P(2) + P(0)=*P(2)
P(3) = *P(2) + P(1)=*P(2)
P(4) = *P(2) + P(2)=*P(2)+*P(2)
P(5) = *P(2) + P(3)=*P(2)+*P(2)
…
我们可以看到对于P（n）问题的n的奇偶问题，实际上p（奇）是等价于p(奇-1)的。也就是说我们不用对奇数做额外的处理。
*扩展了解：我们可以得到更一般的一般形式：
对于 n ≥ 2：
P(n) = P(2) + P(n-2)
def is_palindrome(s):
def P(n, start):
# 基本情况
if n <= 1:
return True
# *P(2): 判断首尾字符是否相同
p2_star = (s[start] == s[start + n - 1])
# 递归调用
return p2_star and P(n - 2, start + 1)
return P(len(s), 0)
主函数代码
我们发现，真要暴力遍历，是个很复杂的过程，因为我们要判断1+2+…+n次，例如对于“abcd”这个字符串，我们要找出所有的字串并遍历的话，
长度为1的子串：
对于一个长度为n的字符串，长度为1的子串有n个。
例如，“abcd” 的长度为1的子串有：[“a”, “b”, “c”, “d”]，共4个。
长度为2的子串：
长度为2的子串有n-1个。
例如，“abcd” 的长度为2的子串有：[“ab”, “bc”, “cd”]，共3个。
长度为3的子串：
长度为3的子串有n-2个。
例如，“abcd” 的长度为3的子串有：[“abc”, “bcd”]，共2个。
依此类推，直到：
长度为n的子串（整个字符串本身）只有1个。
总结这个模式：
长度为1的子串：n个
长度为2的子串：n-1个
长度为3的子串：n-2个
…
长度为n-1的子串：2个
长度为n的子串：1个
数学表达：
总子串数 = n + (n-1) + (n-2) + … + 2 + 1
即等差数列的求和，结果为：n * (n + 1) / 2
这样的暴力写法本身都变得太复杂，我们是不是可以用之前降低问题规模的思路，重新思考一下呢。
我们整理一下思路，因为目的是要找出给定字符串中最长的回文子串。
所以我们算法的主干核心思想如下：
从最长可能的子串开始检查，逐步缩小长度，直到找到一个回文子串。
代码逻辑分解：
a. 从整个字符串长度n开始遍历到0。【最外层循环】
for length in range(n, 0, -1):
# todo
b. 检查所有该长度的子串是否为回文。 【内层循环】
for start in range(n - length + 1):
if is_palindrome(s[start:start+length]):
# todo
c. 如果找到回文，立即返回。【结束】
for start in range(n - length + 1):
if is_palindrome(s[start:start+length]):
return s[start:start+length]
d. 如果没有找到，最后返回空值【边界处理】
return ''
实现策略：
外层循环控制子串长度，从最长到最短。
内层循环遍历所有可能的起始位置。
使用之前的辅助函数is_palindrome检查子串是否为回文。
那么最后我们可以得到我们的粗糙版本算法
思路1 粗糙版本的最终代码
class Solution:
def longestPalindrome(self, s: str) -> str:
def is_palindrome(start, end):
while start < end:
if s[start] != s[end]:
return False
start += 1
end -= 1
return True
n = len(s)
# 从最长的可能长度开始
for length in range(n, 0, -1):
# 检查所有这个长度的子串
for start in range(n - length + 1):
if is_palindrome(start, start + length - 1):
return s[start:start+length]
# 如果没有找到回文（这种情况实际上不会发生，因为单个字符总是回文）
return ""
提交结果
测试通过啦！恭喜我们，成功解决了一个问题，虽然还不是最优的，但是作为初学者，我们已经很厉害了！
（我们的解法不是最优的，如果出现下面的结果，只是运气好而已，不要骄傲哦！）
思路2 动态规划
有人想听吗
思路3 Manacher算法
点赞达到100就更新（疯狂画饼）
原文地址：https://blog.csdn.net/crazyjinks/article/details/142832578
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！