LeetCode 5. 最长回文子串

2019-02-20  本文已影响0人  liulei_ahu

5. 最长回文子串

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


示例1

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

示例2

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

解题思路

方法1 动态规划

定义dp[i][j]如下,dp[i][j]=\left\{ \begin{aligned} &True ,子串s[i,...,j]是回文串\\ &False , else \end{aligned} \right.
dp[i][j] = dp[i-1][j+1] \&\& s[i-1] == s[j+1]
找到满足dp[i][j] == True的最长的s[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

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

方法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]

时间复杂度为O(n^2), 空间复杂度为O(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

以上表为例,s[3] = 2, 回文串长度为2*RL[3] - 1, 其中在该回文串中\#的个数比字母个数多1(在每个回文串中都有此规律), 所以原始串中的回文串长度为2*RL[3] - 1 - RL[3] = RL[3] - 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('#', '')

时间复杂度为O(n), 空间复杂度为O(n)

上一篇下一篇

猜你喜欢

热点阅读