[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 = 0
        while left >= 0 and right < length and s[left] == s[right]:
            sub_len = right - left + 1  # 此时符合回文条件的子字符串长度
            left -= 1
            right += 1
        return 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 = 0
        max_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_2
                max_sub_str = sub_2
            elif len_1 > max_sub_len:
                max_sub_len = len_1
                max_sub_str = sub_1
        return max_sub_str, max_sub_len

if __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 = 0
        sub_end = 0
        sub_len = 0
        length = 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] = True
                    elif dp[i + 1][j - 1]:
                        dp[i][j] = True
                if dp[i][j] and j - i + 1 > sub_len:
                    sub_len = j - i + 1
                    sub_start = i
                    sub_end = j
        return 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 = 0
        max_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_s
                    max_sub_length = sub_length
        return max_sub_s, max_sub_length

仅作为代码记录，方便自学自查自纠