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".

Solution1

首先可以想到的方法是暴力解法，枚举所有子串，对每个子串判断是否为回文，复杂度为O\(n^3\)，所以不推荐，比较容易想的解法是以当前的点为左右指针的两个点，然后左右移动，然后去比较当前最长的回文，如果大于就覆盖当前的最大回文的变量， 需要注意的就是有奇偶的情况。时间复杂度是：O(N)

class Solution:
    # @param {string} s input string
    # @return {string} the longest palindromic substring
    def longestPalindrome(self, s):
        if s == None or len(s) == 1:
            return s
        # Write your code here
        result = ''
        for i in range(len(s)):
            left, right = i, i + 1
            while left >= 0 and right < len(s) and s[left] == s[right]:
                if right - left + 1 > len(result):
                    result = s[left: right + 1]
                left -= 1
                right += 1

            left, right = i - 1, i + 1
            while left >= 0 and right < len(s) and s[left] == s[right]:
                if right - left + 1 > len(result):
                    result = s[left: right + 1]
                left -= 1
                right += 1

        return result

Solution 2

DP 方法，区间型动态规划的典型应用，在里面可以使用滑动变量，来不断更新最长字符串。比较tricky的地方是i + 1 > j -1的情况，有两种做法，可以一开始就初始化，从i 到j 只有一个或者两个元素的情况，或者把i + 1 > j - 1带入表达式，这样第二层的循环j 从 等于i 开始，否则如果前面初始化了，则可以直接从j = i + 2 -> n 开始循环。

class Solution:
    # @param {string} s input string
    # @return {string} the longest palindromic substring
    def longestPalindrome(self, s):
        # Write your code here
        n = len(s)
        longest = ''
        isPalin =  [[False for y in range(n)] for x in range(n)]
        # i + 1 > j -1 说明从i到j只有一个或者两个元素的时候，不需要进行isPalin[i][j] 判断。
        # 如果不进行i + 1> j- 1的判定，也可以初始化，i到j的一个到两个元素。

        for i in range(n - 1, -1, -1):
            for j in range(i, n):
                if (i + 1 > j - 1 or isPalin[i + 1][j - 1]) and s[i] == s[j]:
                    isPalin[i][j] = True
                    if len(s[i: j + 1]) > len(longest):
                        longest = s[i: j + 1]
        return longest

Solution 3

后缀法：

Solution 4

Manacher（马拉车） 算法， 这个不好想，也不好背诵，果断放弃。