关于leetcode:Leetcode5-最长回文子串

题目要求

• 思路：

  • 如果 a 是回文字符串，那么如果 a 的左侧字符 = a 的右侧字符，【a 左侧字符 +a+ a 的右侧字符】也是一个回文串
  • 同理，如果 bab 是回文字符串，那么 如果最左侧 b 的左侧字符 = 最右侧的 b 的右侧字符，那么【最左侧 b 的左侧字符 + bab + 最右侧的 b 的右侧字符】也是一个回文字符串

  • 所以能够编写一个函数 get_str，给定已知回文子字符串的最小下标和最右下标，而后横向扩散去寻找回文字符串。

    • 例如 字符串 s = “babad”，b 的下标为 2，b 为一个回文子字符串，那么把 2 作为字符串的左下标 left，2 同时作为字符串的右下标 right，让函数 get_str 去向左向右寻找，如果 left > 0 and right < len(s) and s[left] == s[right]，就让 left – 1，right + 1，而后在比拟 s[left-1] 与 s[right+1] 是否相等，且下标不超过 0 和 len(s)

  • 那么如何确定要给 get_str 什么样的下标呢，能够通过遍历字符串 s

    • 每遍历到一个字符，有两种状况

      • 1、这个字符是核心字符，例如 bab，a 就是核心字符，那么给 get_str 的左下标和右下标都是 a 的下标
      • 2、这个字符和这个字符的下一个字符独特组成核心字符，例如，baab，那么给 get_str，左侧 a 的下标作为左下标，右侧 a 的下标作为右下标
  • 还须要有两个变量，start，end，用来保留以后最长子回文串的左下标和右下标，如果 get_str 找到比以后长期保留的子字符串更长的回文串，要更新 start 和 end，最初返回 s[start,end + 1]（因为 s[start:end] 会不算上 end）
• 外围代码

class Solution:
    def longestPalindrome(self, s: str) -> str:
        
        def get_str(left, right, s):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            # 返回 left+ 1 和 right- 1 是因为最初一次 while 循环会对 left 多减一，对 right 多 +1，这时的 left 和 right 左右会多各多算一个字符
            return left + 1, right - 1
        
        start, end = 0, 0
        for i in range(len(s)):
            # 两种状况
            left1, right1 = get_str(i, i, s)
            left2, right2 = get_str(i, i + 1, s)
            # 如果搜寻到比以后回文子字符串更长的，就要更新
            if right1 - left1 > end -start:
                start, end = left1, right1
            if right2 - left2 > end -start:
                start, end = left2, right2
        return s[start:end + 1]

残缺代码

class Solution:
    def longestPalindrome(self, s: str) -> str:
        
        def get_str(left, right, s):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return left + 1, right - 1
        
        start, end = 0, 0
        for i in range(len(s)):
            left1, right1 = get_str(i, i, s)
            left2, right2 = get_str(i, i + 1, s)
            if right1 - left1 > end -start:
                start, end = left1, right1
            if right2 - left2 > end -start:
                start, end = left2, right2
        return s[start:end + 1]