python刷LeetCode：5. 最长回文子串

难度等级：中等

题目描述：

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：

输入: "cbbd"
输出: "bb"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

此题有多重解法，笔者作为小菜，目前只对自己想到的解法做说明：

1、回文子串的定义：字符串倒序和正序相等的字符串，即正着念和倒着念一样，如：上海自来水来自海上

2、笔者解法是遍历字符串每个字母，然后以每个字母为中心来判断两边的字符是否相等（分奇偶情况，奇数是字符完全在中间。偶数是字符属于中间2个中的左边那个）

更多方法可以参考这位力友做的分析，分析比较全面：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode/

解题代码：

class Solution:

    def longestPalindrome(self, s: str) -> str:

        longest_len = 0  # 最长回文子串长度

        longest_str = ''  # 最长回文子串

        len_s = len(s)

        for i, letter in enumerate(s):

            str1 = ''

            flag = 1

            for j in range(0, i+1):

                if i+1+j<len_s:

                    if s[i-j] == s[i+1 +j] and flag==1:  # 偶对称

                        str1 = s[i-j] + str1 + s[i+1 +j]

                        current_len = len(str1)

                        if current_len > longest_len:

                            longest_len = current_len

                            longest_str = str1

                    else:

                        flag = 0

                        break

            str2 = letter

            flag = 1

            for j in range(1, i+1):

                if i + j < len_s:

                    if s[i-j] == s[i+j] and flag==1:  # 奇对称

                        str2 = s[i-j] + str2 + s[i+j]

                        current_len = len(str2)

                        if current_len > longest_len:

                            longest_len = current_len

                            longest_str = str2

                    else:

                        flag = 0

                        break

        if not longest_str:

            try:

                longest_str = s[0]  # 输入一个字符的情况

            except:

                longest_str = ''  # 解决输入为空的情况

        return longest_str

巴特西

python刷LeetCode：5. 最长回文子串

难度等级：中等

题目描述：

解题思路：

解题代码：

最新文章

热门文章