数组
给你一个字符串 s,找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。
示例 1:
输入:s = “babad”
输出:“bab”
解释:“aba” 同样是符合题意的答案。
示例 2:
输入:s = “cbbd”
输出:“bb”
1.第一次实现
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
max_length = 2
max_str = None
for stride in range(2,len(s)+1):
flag = 0
while not flag:
for i in range(len(s)):
temp_str = s[i:i+stride]
if len(temp_str)%2 and i+stride <= len(s):
# 判断单数单元
step = 0
for j in range(0,len(temp_str)//2):
if temp_str[j] == temp_str[len(temp_str)-1-j]:
# 如果发现窗口单元不是回文字符串,则函数继续执行
step+=1
if step*2 ==len(temp_str)-1:
flag = 1
if stride > max_length:
max_length = stride
max_str = temp_str
else:
flag = 0
else:
# 判断双数单元
step = 0
win_length = len(temp_str)
for j in range(0,win_length//2):
if temp_str[j] == temp_str[win_length-j-1] :
# 如果发现窗口单元不是回文字符串,则函数继续执行
step+=1
if step*2 ==len(temp_str):
flag = 1
if stride >= max_length:
max_length = stride
max_str = temp_str
else:
flag = 0
return max_str
2.参考代码
- 首先设置初始的回文字符串’’
- 设定起始的滑动窗口,根据res的大小控制其实质,根据i来控制遍历的窗口大小
- 当窗口字符串为奇数时,判定其字符串与倒序字符串是否相同,若相同更新回文字符串大小与start起始位置
- 这里使用了temp[::-1]数组倒序
- temp = temp[1:],回文字符串自身规律
class Solution(object):
def longestPalindrome(self, s):
res = ''
for i in range(len(s)):
start = max(i - len(res) -1, 0)
temp = s[start: i+1]
if temp == temp[::-1]:
res = temp
else:
temp = temp[1:]
if temp == temp[::-1]:
res = temp
return res
作者:雨晨GG
链接:https://leetcode.cn/problems/longest-palindromic-substring/solutions/1601761/by-yu-chen-gg-kz5y/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
3.原有代码修改
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
# 极端案例'ab',这个字符串的回文字符串为'a'
if len(s)==2 and s!=s[::-1]:
return s[0]
### 以下处理通用案例,将回文字符串划分为两种情况
### 回文字符串为单数与回文字符串为偶数
#初始化回文字符串
max_length = 1
max_str = ""
# 外层循环控制滑动窗口步长
for stride in range(1, len(s) + 1):
# 内层循环控制窗口移动范围范围:注意窗口移动范围不能越界
for i in range(len(s) - stride + 1):
# 提取窗口字符串
temp_str = s[i:i+stride]
#分不同情况进行判定,若发现回文字符串,则跳出内部循环,更新步长与回文字符串,直至遍历所有长度类型的回文字符串。
if stride % 2 :
# 判断单数单元
if temp_str == temp_str[::-1]:
# 发现回文字符串
if stride >= max_length:
max_length = stride
max_str = temp_str
break
else:
# 判断双数单元
if temp_str == temp_str[::-1]:
flag = 1
if stride >= max_length:
max_length = stride
max_str = temp_str
# 跳出内层循环
break
return max_str
在测试算法过程中,1)列表转置操作可以有效提高计算效率;2)如果不设置字符创移动边界,会增加算法的计算量,字符串越界回返回错误结果),3)我将return写到内层循环中,每次跳出时,直接返回了函数结果;平常习惯直接调用api,需要多熟悉一些数组的基本操作。