LeetCode 5. 最长回文子串(Longest Palin
2019-08-05 本文已影响0人
leacoder
LeetCode.jpg
5. 最长回文子串
5. 最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
切题
一、Clarification
求最长回文子串，这里有几个特殊情况需要考虑
1、空字符串， "" ，最长回文子串 ""
2、单个字符，"a"，最长回文子串 "a"
3、两个字符，"ab"，最长回文子串 "a"或者"b"
两个字符，"cc"， 最长回文子串 "cc"
二、Possible Solution
1、暴力求解
从最长字符串开始扫描
2、动态规划
状态定义、状态转移方程
Python3
暴力求解
# @author:leacoder
# @des: 暴力求解 最长回文子串
'''
从最长字符串开始扫描（最长子串就是其本身）子串个数为 1，如果不是回文 子串长度-1，子串个数+1
子串长度 子串个数
n 1
n-1 2
. .
. .
2 n-1
1 n
'''
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
if 0 == n:
return null
for i in range(n): # i = 0 时为最长子串，长度n ；i = 1时 子串长度n-1子串个数2
start = 0
end = n - i # n-i 长度子串中，第一个子串的起始位置
while end <= n:
sub_string = s[start:end] # 子串
# 判断是否回文
if self.is_palindromic_string(sub_string):
return sub_string
# 遍历长度为 n-i 的所有子串
start += 1
end +=1
def is_palindromic_string(self,s):
return s == s[::-1]
动态规划
# @author:leacoder
# @des: 动态规划 最长回文子串
'''
动态规划分析
一、状态定义
dp[l][r] 表示子串s[l,r] (包括区间l 和 r, l 表示子串左边索引，r 表示子串右边索引) 是否是回文，也就是如果s[l,r]是回文字符串，则有dp[l][r] = true
二、状态转移方程
1、如果s[l+1,r-1]长度大于 1,也就是 r-1 - (l+1)>0 -> r - 1 > 2 时，dp[l+1][r-1]=true 并且 s[l] == s[r] 那么 s[l,r] 为回文字符串 dp[l][r] = true
s[l+1,r-1]为回文字符串，只有当s[l] == s[r]时 s[l,r] 才为回文字符串
2、如果s[l+1,r-1] 长度为 1 也就是 r-1 - (l+1) = 0 -> r - l = 2 时 并且 s[l] == s[r] 那么 s[l,r] 为回文字符串 dp[l][r] = true
3、如果s[l+1,r-1] 为空字符串小于1也就是 r-1 - (l+1)< 0 -> r - l < 2，并且 s[l] == s[r] 那么 s[l,r] 为回文字符串，dp[l][r] = true
2 和 3合并为一个条件 r - l <= 2 并且 s[l] == s[r]
所以 综上状态转移方程 为
s[l] == s[r] and (r -1 <= 2 or dp[l + 1, r - 1]) 那么 dp[l, r] = = true
'''
'''
特殊情况
当s字符串长度<=1时，其本身必然为回文字符串
'''
class Solution:
def longestPalindrome(self, s: str) -> str:
# 特殊情况
size = len(s)
if size <= 1:
return s
# 状态 初始化 dp[l,r] 二维状态，初始化为False
dp = [[False for _ in range(size)] for _ in range(size)]
# 最长回文子串
max_length = 0
# max_substring = ""
max_substring = s[0] # 兼容处理 "ab" 这种情况
# <=1 的情况 已在特殊情况中处理
for r in range(1,size):
for l in range(r):
if s[l] == s[r] and (r - l <= 2 or dp[l + 1][r - 1]):
dp[l][r] = True
cur_length = r - l + 1 # 当前回文字符串长度
if cur_length > max_length:
max_length = cur_length
max_substring = s[l:r+1] # r+1取不到
return max_substring
GitHub链接：
https://github.com/lichangke/LeetCode
个人Blog:
https://lichangke.github.io/
欢迎大家来一起交流学习
