0005. Longest Palindromic Substring

Medium | String + DP | 80 ms (99.34%), 13.5 MB (92.93%)

❓ Problem Statement

Source: LeetCode - Longest Palindromic Substring GitHub: Solution / Performance

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

✍🏻 Constraints & Example

💡 Ideas

Whether a string is palindromic depends on the previous two chars from the left and right. Thus, we could adopt dynamic programming with a memo to solve this problem.

A two-dimension array is initialized to store whether s[j:i] is a palindromic string by recording as dp[i][j] = True. Then, we iterate the input string by a nested for loop which range is from i = len(s) and j = i+1.

In each iteration, there are three different conditions to help us check palindrome:

1. if i == j, dp[i][j] = True

2. if i == j + 1, dp[i][j] = s[i] == s[j]

3. else, dp[i][j] = (dp[i-1][j+1] and s[i] == s[j])

Note that condition 3 checks whether the shrunk string s[j+1:i-1] is a palindrome string and whether s[i] == s[j]

🤖 Python3 (DP)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # (base case)
        if len(s) < 2: return s

        # ==================================================
        #  Dynamic Programming                             =
        # ==================================================
        # time  : O(n^2)
        # space : O(n^2)
        
        ret = ''
        
        # dp[i][j] = True mean s[j:i] = Palindrome
        dp = [[None] * len(s) for i in range(len(s))]
        
        for i in range(len(s)):
            for j in range(i+1):
                if i == j: dp[i][j] = True
                elif i == j+1: dp[i][j] = s[i] == s[j]
                else: dp[i][j] = (dp[i-1][j+1] and s[i] == s[j])
                
                if dp[i][j] and i - j + 1 > len(ret): ret = s[j:i+1]
                    
        return ret

🤖 Python3 (non-DP)

🤖 Java