5.最长回文子串
给你一个字符串 s
,找到 s
中最长的回文子串。
暴力解法:
- 枚举出s的所有子串的左下标值和其长度
- 判断字串是否是回文字串
- 截取子串(begin:begin+maxLen)
第2,3步在算法中都类似,重要的是怎么简化第1步。
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
# 判断 回文子串 的算法
def validPalindromic(s,left,right):
while left < right:#逐个比较左右侧值是否相等
if s[left]!=s[right]:
return False
left+=1
right-=1
return True
n = len(s)
# 判断长度为1的字符串
if n<2:
return s
maxLen = 1
begin = 0
#枚举 所有长度严格大于1的字串,p[i...j]
for i in range(n-1):#右边界前一位
for j in range(1,n):#左边界后一位
if (j-i+1 > maxLen and validPalindromic(s,i,j)):
maxLen = j-i+1 #子串长度递增
begin = i #左边界右移
return s[begin:begin+maxLen]
时间复杂度:,空间复杂度:
中心扩展算法:从中心考虑
- 将第1步简化为:枚举出所有中心字符串的中心位置和长度,需考虑子串长度为奇数、偶数的情况
- 判断:在左侧向左移动,右侧向右移动,且左右端值相等时,该子串为回文子串
class Solution(object):
#中心扩散方法,判断是否为回文子串
def expandAroundCenter(self, s,left,right):
while left>=0 and right<len(s) and s[left] == s[right]:
left-=1
right+=1
return left+1,right-1 #最后一步是条件不满足退出循环,所以下标值收缩一步
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
start,end = 0,0
for i in range(len(s)):
left1,right1 = self.expandAroundCenter(s,i,i)#偶数回文子串
left2,right2 = self.expandAroundCenter(s,i,i+1)#奇数回文子串
if right1 - left1 > end-start:
start,end = left1,right1
if right2-left2 > end-start:
start,end = left2,right2
return s[start:end+1]
时间复杂度:,空间复杂度:
动态规划:
回文子串状态转移的性质:在左右字符相同的情况下,中间字符串决定了子串是否属于回文子串。
例如一个字符串m:m[0]==m[3],且m[1:2]是回文序列,则m[1:3]是回文序列;m[2]==m[5],且m[3:4]不是回文序列,则m[2:5]不是回文序列。
对于字符串的子串P(i,j),可以用如下表格记录子串是否是回文子串,根据表格可以看出,s[0:2]和s[1:3]都是回文子串。
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
n = len(s)
if n<2:
return s
maxLen = 1
begin = 0
# 创建一个n*n的表格,初始化表格内容为False
dp = [[False]*n for _ in range(n)]
# 对角线元素都是回文子串
for i in range(n):
dp[i][i] = True
# 枚举子串长度
for L in range(2,n+1): #n=6,n+1=7,L=2,3,4,5,6
for i in range(n):
# 右边界j
j = L+i-1
if j>=n:
break
if s[i]!=s[j]:
dp[i][j]=False
else:
if j-i<3:
dp[i][j]=True
else:
dp[i][j]=dp[i+1][j-1]
if dp[i][j] and j-i+1>maxLen:
maxLen = j-i+1
begin = i
return s[begin:begin+maxLen]
时间复杂度:,空间复杂度:
6.Z字形变换
将一个给定字符串 s 根据给定的行数 numRows ,以从上往下、从左到右进行 Z 字形排列。
矩阵填充
定义一个r*c的空矩阵,使用循环将s中的值以Z字型填入矩阵。输入字符串为 "PAYPALISHIRING" 行数为 3 时,排列如下:
- 首先根据行数确定Z字变换的周期t,再求出行数c,这里的c比实际占用行数多一行
- 遍历字符串s,当 s 下标 i 对周期 t 取余小于r-1时向下移动,否则向右上移动
class Solution(object):
def convert(self, s, numRows):
"""
:type s: str
:type numRows: int
:rtype: str
"""
n = len(s)
if numRows < n:return s
t = numRows * 2 - 2
c = (n + t - 1) // t * (numRows - 1)
mat = [[''] * c for _ in range(numRows)] #创建空矩阵,c列,numRows行
x, y = 0, 0
for i, ch in enumerate(s):
mat[x][y] = ch
if i % t < numRows - 1: #Z字移动的判断条件
x += 1 # 向下移动
else:
x -= 1
y += 1 # 向右上移动
return ''.join(ch for row in mat for ch in row if ch) #取出非空字符
本文含有隐藏内容,请 开通VIP 后查看