Longest Palindrome Substring

题目描述

解题方法

都TLE……

dfs + 记忆化搜索的方法

可以作对，将check isPalindrome的结果存下来，但是过不了时间

正常DP的做法

dp[i][j] 表示s[i:j+1]是会文

转换方程

if j == i + 1and s[i] == s[j]:
    dp[i][j] = True
elif s[i] == s[j] and dp[i+1][j-1]:
    dp[i][j] = True

init status

每个字符自身是一个palindrome

Solution

记忆化搜索的方法

class Solution:
    # @param A : string
    # @return a strings
    def longestPalindrome(self, A):
        s = A
        if not s:
            return ""
        self.s_map = {}
        length = len(s)
        if length == 0 or length == 1:
            return s
        max_length = 1
        max_substring = s[0]

        for i in range(length):
            for j in range(i+1, length):
                if j == i+1 and s[i] == s[j]:
                    if max_length < 2:
                        max_length = 2
                        max_substring = s[i:j+1]
                else:
                    if s[i] == s[j] and self.isPalindrome(s[i+1:j]):
                        if max_length < j - i + 1:
                            max_length = j - i + 1
                            max_substring = s[i:j+1]
        return max_substring

    def isPalindrome(self, s):
        if s in self.s_map:
            return self.s_map[s]

        length = len(s)
        if length == 0 or length == 1:
            self.s_map[s] = True
            return True
        start = 0
        end = length - 1
        while start < end:
            if s[start] != s[end]:
                self.s_map[s] = False
                return False
            start += 1
            end -= 1
        self.s_map[s] = True
        return True

DP

class Solution:
    # @param A : string
    # @return a strings
    def longestPalindrome(self, A):
        s = A
        length = len(s)
        if length == 0 or length == 1:
            return s
        max_length = 1
        max_substring = s[0]

        dp = [[False for i in range(length)] for j in range(length)]
        for i in range(length):
            dp[i][i] = True

        for i in range(length):
            for j in range(i): # order is important!
                if j + 1== i:
                    if s[i] == s[j]:
                        dp[j][i] = True
                        if max_length < 2:
                            max_length = 2
                            max_substring = s[j:i+1]
                else:
                    if s[i] == s[j] and dp[j+1][i-1]:
                        dp[j][i] = True
                        if max_length < i - j + 1:
                            max_length = i - j + 1
                            max_substring = s[j:i+1]
        return max_substring

Reference