Longest Palindrome Substring

题目描述

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.

解题方法

brute force

i,j 确定一个substring,然后再check这个substring是否是palindrome。

时间复杂度是O(n^2 * n) = O(n^3)

DP

在brute中有很多重复计算，并且两个palindrome之间是有关系的，所以很容易可以 往DP的方向想。

state

dp[i][j]表示从i到j的substring是否为palindrome

function

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

这里要求j < i并且dp[j+1][i-1]在dp[j][i]之前就已经计算出来了，所以 i应该从0到length的遍历，而j从0到i遍历，只有j == i - 1的情况需要特殊处理，因为之前 的一个loop里j达不到这个i-1.

  • 时间复杂度O(n^2)
  • 空间复杂度O(n^2)

确定pivot, 两边扩展

对于每个i，确定pivot向两边扩展找最大的palindrome

注意点

  • palindrome长度可以是奇数也可以是偶数
  • 奇数的话pivot就是s[i]

  • 偶数的话pivot就应该确定为i-1, i的中间

  • 时间复杂度O(n^2)

  • 空间复杂度O(1)

Solution

DP

方法正确，但是过不了test case, time limit exceeds

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if not s:
            return ""

        result = ""
        length = len(s)
        if length == 1:
            return 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]

        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 s[i] == s[j] and dp[j+1][i-1]:
                        dp[j][i] = True
                        if len(result) < i - j + 1:
                            result = s[j:i+1]

        return result

确定中心往两边扩展

可以过test case

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if not s:
            return ""

        result = ""
        length = len(s)
        if length == 1:
            return s

        for i in range(1, length):
            # center is between i - 1, i
            # 长度为偶数的palindrome
            low, high = i - 1, i
            while low >= 0 and high < length and s[low] == s[high]:
                low -= 1
                high += 1

            curLen = (high - 1) - (low + 1) + 1
            if curLen > len(result):
                result = s[low+1:high]

            # center is i
            # 长度为奇数的palindrome
            low, high = i - 1, i + 1
            while low >= 0 and high < length and s[low] == s[high]:
                low -= 1
                high += 1

            curLen = (high - 1) - (low + 1) + 1
            if curLen > len(result):
                result = s[low+1:high]

        return result

Reference