5. Longest Palindromic Substring

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

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res = []
        self.backtrack(s, start=0, path=[], res=res)
        return res

    def backtrack(self, s, start, path, res):
        if start == len(s):
            res.append(path)
            return

        for end in range(start + 1, len(s) + 1):
            sub = s[start: end]
            if sub == sub[::-1]:    #isPalindrome
                self.backtrack(s, end, path + [sub], res)

前に解いた131. Palindrome Partitioningの問題を適用して解決してみました...失敗

Solution 1: Runtime: 4184 ms - 26.55% / Memory Usage: 22.2 MB - 8.97%

class Solution:
    def longestPalindrome(self, s: str) -> str:
        
        n = len(s)
        # Form a bottom-up dp 2d array
        # dp[i][j] will be 'true' if the string from index i to j is a palindrome. 
        dp = [[False] * n  for _ in range(n)]
        
        ans = ''
        # every string with one character is a palindrome
        for i in range(n):
            dp[i][i] = True
            ans = s[i]
            
        maxLen = 1
        for start in range(n-1, -1, -1):
            for end in range(start+1, n):             
				# palindrome condition
                if s[start] == s[end]:
                    # if it's a two char. string or if the remaining string is a palindrome too
                    if end - start == 1 or dp[start+1][end-1]:
                        dp[start][end] = True
                        if maxLen < end - start + 1:
                            maxLen = end - start + 1
                            ans = s[start: end+ 1]
        
        return ans

DPの使い方

最初はn*nで、Falseで埋め込まれ、1文字(dp[i][i])のTrueです.

startとendの値を使用startは上部から逆順に並び、endはstartの右側から順番に並びます

二人が同じなら返事です.この部分を知らない

maxLen更新ごとにansも更新されます

今はまだいつDPを使うのがとても悲しいことを知りません