005._longest_palindromic_substring.md

###5. Longest Palindromic Substring

题目: https://leetcode.com/problems/longest-palindromic-substring/

难度:

Medium

思路0:

暴力解法绝对不行

思路1:

所以一个好的想法是 s 和 reverse(s) 共有的最长的 substring就是longest palindromic substring -> 问题转成求Longest common substring problem 参见wikipedia ，典型动归

LCSuff(S1...p, T1...q) = LCS(S1...p1, T1...q-1) if S[p] = T[q] else 0

伪码也有了，代码也有：

https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_substring#Python_2

这样也超时？

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        def lcs(s1, s2):
            m = [[0] * (1 + len(s2)) for i in xrange(1 + len(s1))]
            longest, x_longest = 0, 0
            for x in xrange(1, 1 + len(s1)):
                for y in xrange(1, 1 + len(s2)):
                    if s1[x - 1] == s2[y - 1]:
                        m[x][y] = m[x - 1][y - 1] + 1
                        if m[x][y] > longest:
                            longest = m[x][y]
                            x_longest = x
                    else:
                        m[x][y] = 0
            return s1[x_longest - longest: x_longest]

        return lcs(s, s[::-1])

因为以为这样s[::-1]已经很快了.

这个方法是buggy的，看字符串abcxgcba,它reverse之后是abcgxcba,它们有公共字符串，但是这里面没有回文，修复方式是：

we check if the substring’s indices are the same as the reversed substring’s original indices. If it is, then we attempt to update the longest palindrome found so far; if not, we skip this and find the next candidate.

我觉得的修复方式这样么：

原本     翻转
ABXYBA   ABYXBA

求出来的substring indices是 0:2 但是这个s1[0:2] 和 s2[0:2]一样，所以不行
同理common substring indices还是s[4:6] 和s2[4:6]一样，不行

而比如ABAD和 DABA

substring indice 一个是0：3， 一个是1:4，这样就没问题

思路2:

依次把每一个字符当做回文字符串的中间字符，找到以该字符为中间字符的回文串的最大长度。分别对奇偶的情况进行讨论，接下来的关键就是对边界的把握，确保下标不要越界。当子串已经包含首字符或最后一个字符且此时还是回文串的时候，下标分别会向两边多移一位，需要补回来。

参考https://shenjie1993.gitbooks.io/leetcode-python/content/005%20Longest%20Palindromic%20Substring.html

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        n = len(s)

        # empty or one char
        if n < 2:
            return s

        # left index of the target substring
        l = 0
        # right index of the target substring
        r = 0
        # length of the longest palindromic substring for now
        m = 0
        # length of the current substring
        c = 0

        # Whether the substring contains the first character or last character and is palindromic
        b = True
        for i in range(n):
            # Odd situation
            for j in range(min(n-i,i+1)):
                if s[i-j] != s [i+j]:
                    b = False
                    break
                else:
                    c = 2 * j + 1

            if c > m :
                l = i - j + 1 - b
                r = i + j + b
                m = c 
            b = True

            # Even situation
            for j in range(min(n - i - 1, i + 1)):
                if (s[i - j] != s[i + j + 1]):
                    b = False
                    break
                else:
                    c = 2 * j + 2
            if (c > m):
                l = i - j + 1 - b
                r = i + j + 1 + b
                m = c
            b = True
        return s[l:r]

以上是参考版本，自己写的版本：

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        n = len(s)

        m,l,r = 0,0,0

        for i in range(n):
            # odd case
            for j in range(min(i+1,n-i)):
                if s[i-j] != s[i+j]:
                    break
                if 2*j + 1 > m :
                    m = 2 * j + 1
                    l = i-j
                    r = i+j


            if i+1 < n and s[i] == s[i+1]:
                for j in range(min(i+1,n-i-1)):
                    if s[i-j] != s[i+j+1]:
                        break
                    if 2 * j + 2 > m :
                        m = 2*j +2
                        l = i-j
                        r = i+j+1


        return s[l:r+1]

思路3:

在查看wikipedia，有一个Longest palindromic substring, 有一个Manacher算法，to be 学