【字符串】最长回文子串
程序员文章站
2022-03-26 13:29:40
想要看更加舒服的排版、更加准时的推送关注公众号“不太灵光的程序员”每日八点有干货推送,微信随时解答你的疑问5 最长回文子串 python3中等 字符串给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 1:输入: “babad”输出: “bab”注意: “aba” 也是一个有效答案。示例 2:输入: “cbbd”输出: “bb”分析过程回文串 就是 正序和逆序是一个结果的字符串叫回文串最长回文子串 是找出 在字符串中 正序和逆序是一....
想要看更加舒服的排版、更加准时的推送
关注公众号“不太灵光的程序员”
每日八点有干货推送,微信随时解答你的疑问
5 最长回文子串 python3
中等
字符串
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1:
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2:
输入: “cbbd”
输出: “bb”
分析过程
回文串 就是 正序和逆序是一个结果的字符串叫回文串
最长回文子串 是找出 在字符串中 正序和逆序是一个结果的子串
# 86%
# 执行用时:812 ms
# 内存消耗:13.7 MB
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
if n < 2: return s
max_len = 0
start_index = 0
def hw_len(left, right):
while left >= 0 and right < n and s[left] == s[right]:
left -= 1
right += 1
return right - left - 1, left + 1
# 中心扩散法
for i in range(n-1):
# 单核心
len1, start_index1 = hw_len(i, i)
# 双核心
len2, start_index2 = hw_len(i, i+1)
if len1 > max_len:
max_len = len1
start_index = start_index1
if len2 > max_len:
max_len = len2
start_index = start_index2
return s[start_index: start_index+max_len]
s = Solution()
st = "cbbd"
ret = s.longestPalindrome(st)
print(ret, 'bb')
st = "babad"
ret = s.longestPalindrome(st)
print(ret, 'bab')
st = "abcda"
ret = s.longestPalindrome(st)
print(ret, "a")
st = "ac"
ret = s.longestPalindrome(st)
print(ret, 'a')
st = "bb"
ret = s.longestPalindrome(st)
print(ret, 'bb')
st = ""
ret = s.longestPalindrome(st)
print(ret)
st = "aacedaa"
ret = s.longestPalindrome(st)
print(ret, "aa")
st = "aacdefcaa"
ret = s.longestPalindrome(st)
print(ret, "aa")
st = "saacdefcaa"
ret = s.longestPalindrome(st)
print(ret, "aa")
st = "abcdbbfcba"
ret = s.longestPalindrome(st)
print(ret, "bb")
st = "onoranynartionso"
ret = s.longestPalindrome(st)
print(ret, "ranynar")
本文地址:https://blog.csdn.net/qq_23934063/article/details/107477318
上一篇: python实现服务器监控报警消息用微信发送(附代码)
下一篇: 分布式架构设计(管理篇)