Longest Palindromic Substring

Question

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Example Given the string = "abcdzdcab", return "cdzdc".

Challenge O(n^2) time is acceptable. Can you do it in O(n) time.

Thoughts

DP, O(n^2)

dp[i][j] 表示 s[i:j]是回文，if only s[i] == s[j] and dp[i+1][j-1] 当计算dp[i][j]时，已经要有dp[i+1][j-1]计算出来 =》 （i比j小, dp[i][j-1]包含了dp[i+1][j-1]) 计算dp[i][j]时，必须已经把dp[i][j-1]计算出来

O(n)算法

Solution

class Solution:
    # @param {string} s input string
    # @return {string} the longest palindromic substring
    def longestPalindrome(self, s):
        # Write your code here
        if not s :
            return ""
        result = ""

        length = len(s)
        dp = [[False for i in range(length)] for j in range(length)]
        for i in range(length):
            dp[i][i] = True
            if len(result) < 1:
                result = s[i]

        #order is very important!!!
        for i in range(length):
            for j in range(i):
                if j == i - 1:
                    if s[i] == s[j]:
                        dp[j][i] = True
                        if len(result) < 2:
                            result = s[j:i+1]
                else:
                    if dp[j+1][i-1]:
                        if s[i] == s[j]:
                            dp[j][i] = True
                            if len(result) < i - j + 1:
                                result = s[j:i+1]

        return result