leetcode5

Posted on | In

5. Longest Palindromic Substring

Description

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

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

Idea

This is interval dp problem. Thus, we should build up a 2-d dp matrix to store information:
dp[i][j] represent whether s[i:j+1] is a palindromic substring or not.

Notice that ‘aa’ and ‘aca’ is palindromic string.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        dp = [[False] * len(s) for _ in range(len(s))]

        max_len = 0
        max_index = (0, 0)
    
        for j in range(len(s)):  # very naive traverse range
            for i in range(0, j + 1):
                if s[i] == s[j] and (j - i <= 2 or dp[i + 1][j - 1]): # j - i <= 2 is the base case in each row, say 'aa' (j = i + 1) or 'a' (j = i)
                    dp[i][j] = True
                if dp[i][j] and j - i + 1 > max_len:
                    max_len = j - i + 1
                    max_index = (i, j)
        print max_index
        return s[max_index[0]:max_index[1] + 1]