5. 最长回文子串

Difficulty
Medium
Tags
字符串
动态规划
URL
https://leetcode-cn.com/problems/longest-palindromic-substring/
Star
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
示例 3：
输入：s = "a"
输出："a"
示例 4：
输入：s = "ac"
输出："a"
提示：
  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母（大写和/或小写）组成
通过次数811,111提交次数2,262,570

法 1 动态规划

思路
区间型动态规划。
定义dp[i][j] 为 s[i:j+1] 是否为回文串。
所以 dp[i][j] = s[i] == s[j] and dp[i+1][j-1], 同时，需要兼顾到 两个字符紧挨着的情况，因为此时只需要判断s[i] == s[j] 即可，没有子问题
整个动态规划即相当于填充如下图所示的表格:
notion imagenotion image
填充的时候，因为dp[i][j] 需要用到 dp[i+1][j-1]，即需要用到当前格子的左下角的格子，所以采用从下到上，从左到右的路径填充。
题解
class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) <= 1:
            return s
        
        dp = [[False] * len(s) for _ in range(len(s))]
				
				# start, end 为闭区间
        # i , j 为闭区间
        start, end = 0, 0
        for i in range(len(s)-1, -1, -1):
            for j in range(i, len(s), 1):
                # 当前两个字符相同 且 ( 两个字符挨着 or 子问题也是回文串)
                if s[i] == s[j] and (i==j or i + 1 == j or dp[i+1][j-1]):
                    if j - i > end - start:
                        start, end = i, j
                    dp[i][j] = True

        return s[start:end+1]

# 上述代码稍微精妙一点，它将dp初始化和状态转移合并到一起了，其实我们可以分开看一下
class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) <= 1:
            return s
        
        dp = [[False] * len(s) for _ in range(len(s))]
        
        # 初始化对角线上的元素为 True 
        for i in range(0, len(s)):
            dp[i][i] = True

        # start, end 为闭区间
        # i , j 为闭区间
        start, end = 0, 0
        for i in range(len(s)-1, -1, -1):
            for j in range(i, len(s), 1):
                # 当前两个字符相同 且 ( 两个字符挨着 or 子问题也是回文串)
                if s[i] == s[j] and (i + 1 == j or dp[i+1][j-1]):
                    if j - i > end - start:
                        start, end = i, j
                    dp[i][j] = True

        return s[start:end+1]

法2 双指针

思路
采用双指针进行扩散。扩散的时候需要考虑如下两种情况：
  • 子串为奇数个。此时双指针初始时指向同一个
  • 子串为偶数个。此时双指针初始时紧挨着
题解
class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) <= 1:
            return s

        start, length = -1, 0
				# 从中间开始扩散
        for mid in range(0, len(s)):
						# 从中间一个字符开始扩散，得到的回文串是奇数个字符
            left, right = mid, mid
            while left >= 0 and right <= len(s)-1 and s[left] == s[right]:
                left -= 1
                right += 1
            if length < right - left + 1 - 2:
                start = left + 1
                length = right - left + 1 - 2
						# 从中间两个字符开始扩散，得到的回文串总是偶数个字符
            left, right = mid, mid + 1
            while left >= 0 and right <= len(s)-1 and s[left] == s[right]:
                left -= 1
                right += 1
            if length < right - left + 1 - 2:
                start = left + 1
                length = right - left + 1 - 2

        return s[start:start+length]


# 优化一下重复代码片段
class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) <= 1:
            return s

        start, length = -1, 0
        for mid in range(0, len(s)):
            length, start = max((length, start), self.helper(s, mid, mid))
            length, start = max((length, start), self.helper(s, mid, mid+1))

        return s[start:start+length]

    def helper(self, s, left, right):
        while left >= 0 and right <= len(s)-1 and s[left] == s[right]:
            left -= 1
            right += 1
        
        return right - left + 1 - 2, left + 1