5. Longest Palindromic Substring

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

solution

• 双指针

class Solution:
    def longestPalindrome(self, s: str) -> str:
        longest = 0
        l = r = 0
        for i in range(len(s)):
            length, left ,right = self.pali(s, i, i)  # 这个写法有点繁杂，只需要返回一个子串，然后选择最长的即可
            if length > longest:
                longest = length
                l = left
                r = right

            length, left, right = self.pali(s, i, i+1)
            if length > longest:
                longest = length
                l = left
                r = right
        return s[l:r+1]

    def pali(self, s, l, r):
        temp_length = 0
        while l >=0 and r < len(s) and s[l] == s[r]:
            if l == r:
                temp_length += 1
            else:
                temp_length += 2
            l -= 1
            r += 1
        return temp_length, l+1, r-1

时间复杂度：O() 空间复杂度：O()

• 动态规划

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        # dp[i][j]: 字符串s[i:j]是否为回文. 虽然目前是最长, 但状态用了是否同时记录起点和长度
        dp = [[True] * n for _ in range(n)]

        start = 0
        res = 1
        for i in range(n - 2, -1, -1):
            for j in range(i + 1, n):
                dp[i][j] = False

                if s[i] == s[j] and dp[i+1][j-1]:
                    dp[i][j] = True
                    if res < j - i + 1:
                        start = i
                        res = j - i + 1
        return s[start: start + res]

follow up-回文类

516. Longest Palindromic Subsequence

# 动态规划
class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        # dp[i][j]: 字符串s[i:j]子字符最长回文
        dp = [[0] * len(s) for _ in range(len(s))]
        for i in range(len(s)):
            dp[i][i] = 1
        
        for i in range(len(s)-1, -1, -1):  # 注意顺序
            for j in range(i+1, len(s)):
                if s[i] == s[j]:
                    dp[i][j] = dp[i+1][j-1] + 2
                else:
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])
        return dp[0][-1]

时间复杂度：O(n^2) 空间复杂度：O(n^2)

647. Palindromic Substrings

131. Palindrome Partitioning

132. Palindrome Partitioning II

2193. Minimum Number of Moves to Make Palindrome

336. Palindrome Pairs

680. Valid Palindrome II

# follow up: 移除最多k个, -> 1216

class Solution:
    def valid_palindrome(self, s: str) -> bool:
        l = 0
        r = len(s) - 1

        while l < r:
            if s[l] == s[r]:
                l += 1
                r -= 1
            else:
                # 关键是这里: 构建一个判断字符串s从l到r位置是否回文的辅助函数
                return self.is_valid(s, l+1, r) or self.is_valid(s, l, r-1)
        return True

    def is_valid(self, s, l, r):
        while l < r:
            if s[l] == s[r]:
                l += 1
                r -= 1
            else:
                return False
        return True

时间复杂度：O(n) 空间复杂度：O(1)

• 超时

class Solution:
    def validPalindrome(self, s: str) -> bool:
        if self.is_valid(s):
            return True

        for i in range(len(s)):
            if self.is_valid(s[:i] + s[i+1:]):
                return True
        return False

    def is_valid(self, s):
        l = 0
        r = len(s) - 1
        while l < r:
            if s[l] != s[r]:
                return False
            l += 1
            r -= 1
        return True

1216 Valid Palindrome III

1930. Unique Length-3 Palindromic Subsequences

Count of Palindromic Substrings