[leetcode]5_最长回文子串
给你一个字符串 s，找到 s 中最长的 回文子串示例 1： 输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。 示例 2： 输入：s = "cbbd" 输出："bb"提示： 1 <= s.length <= 1000 s 仅由数字和英文字母组成
解题思路：【双指针】
参考博文：[leetcode]647_回文子串-CSDN博客
class Solution:def extend(self, s, left, right, length): # 输出每个回文字符串、和对应长度sub_len = 0while left >= 0 and right < length and s[left] == s[right]:sub_len = right - left + 1 # 此时符合回文条件的子字符串长度left -= 1right += 1return s[left + 1: right], sub_len # left - 1和right + 1操作后，才跳出循环，故截取字符串时，需要[left+1:right]def judge_sub_palindrome_index(self,s):length = len(s)max_sub_len = 0max_sub_str = ''for i in range(length):sub_1, len_1 = self.extend(s, i, i, length) # 以i 单个字符扩展sub_2, len_2 = self.extend(s, i, i + 1, length) # 以i , i+1两个字符扩展if len_2 > max_sub_len:max_sub_len = len_2max_sub_str = sub_2elif len_1 > max_sub_len:max_sub_len = len_1max_sub_str = sub_1return max_sub_str, max_sub_lenif __name__ == '__main__':s = input()result_s, result_l = Solution().judge_sub_palindrome_index(s)print(result_s)其他思路：【动态规划】
参考博文：[leetcode]647_回文子串-CSDN博客
def judge_sub_palindrome_dp(self, s):sub_start = 0sub_end = 0sub_len = 0length = len(s)dp = [[False] * length for _ in range(length)]for i in range(length - 1, -1, -1):for j in range(i, length):if s[i] == s[j]:if j - i <= 1:dp[i][j] = Trueelif dp[i + 1][j - 1]:dp[i][j] = Trueif dp[i][j] and j - i + 1 > sub_len:sub_len = j - i + 1sub_start = isub_end = jreturn s[sub_start:sub_end + 1], sub_len其他思路：【暴力思路】
从大到小控制子串长度
然后将每个子串逆序对比
def judge_sub_palindromic_str(slef, s):# 长度递减，for用于遍历字符串长度中的数字3,2,1,0；从大到小控制回文长度,所以返回的第一个回文必是最长回文子串for i in range(len(s), 0, -1):# 分别控制不同长度回文的位置for j in range(0, len(s) - i + 1):# 回文判断if s[j: j + i] == s[j: j + i][::-1]:return s[j: j + i], i其他思路：【暴力思路】
从小到大控制子串长度
判断子串是否回文串
def judge_sub_palindromic_str_I(self, s):lenth = len(s)max_sub_length = 0max_sub_s = ''for i in range(lenth):for j in range(i + 1, lenth):slice_s = slice(i, j)sub_s = s[slice_s]sub_length = len(s[slice_s])# 循环判断字串是否为回文串if sub_s[:] == sub_s[::-1] and sub_length > max_sub_length:max_sub_s = sub_smax_sub_length = sub_lengthreturn max_sub_s, max_sub_length仅作为代码记录，方便自学自查自纠