旭的小窝

5. Longest Palindromic Substring

 
  • 2023年 06月01日

Promble

link: https://leetcode.com/problems/longest-palindromic-substring/

Given a string s, return the longest palindromic substring in s.

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Input: s = "cbbd"
Output: "bb"

Constraints:

  • 1 <= s.length <= 1000
  • s consist of only digits and English letters.

Approach 1

DP

Thought

  • 因为要比较回文，所以先反转字符串。rev = s[::-1]
  • 确定问题：dp[i][j]表示公共子串的长度。
  • string的问题，都是二维数组。所以生成dp[i][j]。i表示S的位置，j表示rev的位置。
  • 状态迁移方程：判断对应的字符是否相等，相等的话， 
    dp[i][j] = dp[i][j] + 1
  • 当i=0或者j=0的时候（即左边和上边），单独分析。字符相等的话就为1。 因为一个字符的字符串，和另一个比的话，最长的长度只能是1.

⚠️ 求出最长公共子串后，并不一定是回文的。 例如，S = ‘abc435cba’ 和 rev = ‘abc534cba’. 最长公共子串是’abc’和’cba’，但是这两个字符串都不是回文串。

所以最后需要判断字符串倒置前的下标和当前的字符串下标是否匹配。 只需要判断末尾字符就可以。

i-dp[i][j]+1 == len(s)-1-j

Code

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) == 0:
            return ""

        rev = s[::-1]
        
        dp = [[0 for _ in range(len(s))] for _ in range(len(s))]

        maxLen = 0
        maxEnd = 0

        for i in range(len(s)):
            for j in range(len(s)):
                if s[i] == rev[j]:
                    # init the up or left edge
                    if i == 0 or j ==0:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = dp[i-1][j-1] + 1

                if dp[i][j] > maxLen:
                    if i-dp[i][j]+1 == len(s)-1-j:
                        maxLen = dp[i][j]
                        maxEnd = i
                    
        # print(dp)
        return s[maxEnd - maxLen+1:maxEnd + 1]

Approach 2

Use python string slice.

Thought

利用python切片的特性可以解这道题。

Code

class Solution:
    def longestPalindrome(self, s: str) -> str:
        m = ''  # Memory to remember a palindrome
        for i in range(len(s)):  # i = start, O = n
            for j in range(len(s), i, -1):  # j = end, O = n^2
                if len(m) >= j-i:  # To reduce time
                    break
                elif s[i:j] == s[i:j][::-1]:
                    m = s[i:j]
                    break
        return m

Reference

  1. https://zhuanlan.zhihu.com/p/55666886
  2. https://zkf85.github.io/2019/03/26/leetcode-005-longest-palindrome
搜索