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 를 사용한 방식

1. 처음엔 n*n 만큼 False 로 채워주고 문자 한개(dp[i][i])의 경우는 모두 True 로 해줌

2. start 와 end 값을 이용해서
   start 는 맨끝에서부터 역순으로 보고 end 는 start 의 오른쪽부터 순서대로 보도록 비교

3. 둘이 같아지면 palindrome 인데... 이부분을 모르겠다

4. maxLen 을 update 할 때마다 ans 도 update 해준다

아직도 DP 를 언제 쓰면 좋을지 모른다는게 슬프네요..