【DP、双指针】5. Longest Palindromic Substring

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Input: "cbbd"
Output: "bb"

class Solution:
    # 方法1：分奇回文串和偶回文串
    def longestPalindrome(self, s: str) -> str:
        if s == "":
            return ""
        lens = len(s)
        maxl = 1
        maxs = s[0]
        for i in range(len(s)):
            es = self.find(s, lens, i, i+1)
            os = self.find(s, lens, i, i+2)
            if len(es) > maxl:
                maxl = len(es)
                maxs = es
            if len(os) > maxl:
                maxl = len(os)
                maxs = os
        return maxs

    def find(self, s, lens, i, j):
        while i >= 0 and j < lens and s[i] == s[j]:
            i -= 1
            j += 1
        return s[i+1:j]

print(Solution().longestPalindrome("aaa")) # "aaa"

class Solution:
    # 方法2：dp[i][j] = True if dp[i+1][j-1] == True and s[i] == s[j]
    def longestPalindrome(self, s: str) -> str:
        if s == "":
            return ""
        lens = len(s)
        maxl = 1
        maxs = s[0]
        dp = [[False] * lens for _ in range(lens)]
        for j in range(lens):
            dp[j][j] = True
            for i in range(j-1, -1, -1):
                if i+1 <= j-1 and dp[i+1][j-1] and s[i] == s[j]:  # 奇回文串
                    dp[i][j] = True
                elif i+1 > j-1 and s[i] == s[j]:  # 偶回文串
                    dp[i][j] = True
                # 如果是回文串，更新最大长度
                if dp[i][j] and j-i+1 > maxl:
                    maxl = j-i+1
                    maxs = s[i:j+1]
        return maxs

print(Solution().longestPalindrome("babad")) # "bad"