LeetCode 5. 最长回文子串

5. 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

---

示例1

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例2

输入: "cbbd"
输出: "bb"

---

解题思路

方法1 动态规划

定义dp[i][j]如下，
故
找到满足的最长的即为最终的结果
代码实现

class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        # dp
        dp = [[False for i in range(len(s))] for j in range(len(s))]
        str = ''
        for i in range(len(s)): # 长度为1
            dp[i][i] = True
            str = s[i] # maxlen = 1
        for i in range(0, len(s)-1): # 长度为2
            if s[i] == s[i+1]:
                dp[i][i+1] = True # maxlen = 2
                str = s[i:i+2]
        for i in range(2,len(s)):
            for j in range(0,len(s)-i):
                if s[j] == s[j+i] and dp[j+1][j+i-1]:
                    dp[j][j+i] = True # maxlen = i+1
                    str = s[j:j+i+1]
        return str

时间复杂度为， 空间复杂度为

方法2 中心扩展算法

从字符串的中心分别向两侧查找，判断是否满足回文条件，需要注意的是奇偶长度的字符串的中心位置有所差异，如'aba'的中心为'b'， 而'abba'的中心为两个'b'之间
代码实现

class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        # 中心扩展算法
        def ismatch(self, s, l, r):
            while(l>=0 and r<len(s) and s[l] == s[r]):
                l = l - 1
                r = r + 1
            return r-l-1
        l = 0
        r = 0
        for i in range(len(s)):
            len1 = self.ismatch(s, i, i)
            len2 = self.ismatch(s, i, i+1)
            length = max(len1, len2)
            if (length > r-l + 1):
                l = i - (length-1)//2
                r = i + length//2
        return s[l:r+1]

时间复杂度为， 空间复杂度为

方法3 Manacher 算法

推荐一篇大牛的简书文章，里面介绍的Manacher算法较为易懂最长回文子串问题—Manacher算法， 补充一下没有解释的一点，为何RL[i]-1 即为原始串中以位置i为对称轴的最长回文串的长度？

index	0	1	2	3	4	5	6	7	8	9	10
s	#	c	#	a	#	b	#	a	#	c	#
RL	1	2	1	2	1	6	1	2	1	2	1

以上表为例，, 回文串长度为， 其中在该回文串中的个数比字母个数多1(在每个回文串中都有此规律)， 所以原始串中的回文串长度为
代码实现

class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        # Manacher 算法
        #预处理
        s='#'+'#'.join(s)+'#'
        RL=[0]*len(s)
        MaxRight=0
        pos=0
        MaxLen = 0
        index = 0
        for i in range(len(s)):
            if i<MaxRight:
                RL[i]=min(RL[2*pos-i], MaxRight-i)
            else:
                RL[i]=1
            #尝试扩展，注意处理边界
            while i-RL[i]>=0 and i+RL[i]<len(s) and s[i-RL[i]]==s[i+RL[i]]:
                RL[i]+=1
            #更新MaxRight,pos
            if RL[i]+i-1>MaxRight:
                MaxRight=RL[i]+i-1
                pos=i
            if RL[i] > MaxLen:
                index = i
                MaxLen = RL[i]
        return s[index-MaxLen+1:index+MaxLen-1].replace('#', '')

时间复杂度为， 空间复杂度为