Leetcode 最长回文子串

Leetcode 最长回文子串

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

示例 1:

输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。

示例 2:

输入: “cbbd”
输出: “bb”

题目是leetcode的第5题,难度系数为中等:

首先简单分析一下思路,回文串是一类很常见的题目。其特点是上海自来水来自海上这种形式。我首先的想到的第一个方法是反转字符串进行比对,如babad,经过反转为dabab对比就可以的到回文串。但是后来发现bafgab反转之后是bagfab会判断ab为回文字符串。因此这个偷鸡方法并不成功。

后来看了花花酱的视频才终于有点思路,首先将代码记录如下:

    def longestPalindrome(self, s):
        maxlength = 0
        p = 0
        # 循环以字符串中的每个字符作为回文的中心,向两侧展开
        for i in range(len(s)):
        	# 考虑两种情况,奇数字符串和偶数字符串
            cur = max(self.getlen(s, i, i), self.getlen(s, i, i+1))
            if cur > maxlength:
                maxlength = cur
                p = i - (maxlength-1)//2
                # 边界条件的计算(x-1)//2对于偶数奇数情况都友好
        return s[p: p+maxlength]

    def getlen(self, s, l, r): # 判断是否为回文字符串,并返回长度
        length = 0
      	# while循环采用了保护性措施,防止边界超出
        while l >= 0 and r < len(s) and s[l] == s[r]:
            r += 1
            l -= 1
        length = r - l - 1 # 注意,此时r,l已经完成移动,位于非回文字符串的位置。需要r-l-2+1。
        return length

代码并不复杂,用到了DP思想,每次得到当前的最大回文字符串长度。但是需要注意几个细节:

  1. 计算回文字符串长度时候,看清楚两个指针的位置
  2. 回文字符串考虑奇偶两种情况,两种情况的中心是不同的
  3. 最后保存回文字符串的开始位置时,p = i - (maxlength-1)//2保证了奇数或者偶数的情况都可以

代码收获:掌握了回文字符串的判断方法!
DP技能点:+1!

上一篇:EFCore通过Include关联清单不存在时返回值为默认值的方式


下一篇:c#-“应用程序配置”文件中的最大键/值长度