LeetCode解题报告(5)--最长回文子字符串

发表于 标签 ， ，

原题如下：

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.

就是要从给定的字符串中找出最大的回文子字符串。

下面介绍两种时间复杂度为 \(O(n^2)\) 的方法，第一种是以每个字符为中心向两边拓展从而得到尽可能长的回文字符串，第二种是利用动态规划。

第一种方法的关键点是以每个字符为中心向两边拓展从而得到尽可能长的回文字符串。这里要注意的是回文字符串的长度可以是奇数也可以是偶数，所以要分两种情况讨论。

实现代码如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#encoding:utf-8
class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        r=s[0]
        if len(s) > 1:
            for i in range (1,len(s)):
                # oddResult
                begin=i 
                end=i
                oddResult=self.getPalindoreStr(s,begin,end)
                if oddResult != None and len(oddResult)> len(r):
                    r=oddResult

                # enevResult
                begin=i-1
                end=i
                evenResult=self.getPalindoreStr(s,begin,end)
                if evenResult != None and len(evenResult)> len(r):
                    r=evenResult
        return r

    #从给定的begin和end位置向两边扩展，得到回文字符串                
    def getPalindoreStr(self,s,begin,end):
        while ( begin>=0 and end<len(s) and s[begin]==s[end] ):
                begin-=1
                end+=1
        result=s[begin+1:end] if  begin+1 <= end else None
        return result

第二种方法采用的是动态规划，dp[i][j] 表示 s[i:j] 所形成的字符串是否为回文字符串，时间复杂度为 \(O(n^2)\)。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        n = len(s)
        dp = [[False for j in xrange(n)] for i in xrange(n)]
        result = ''
        for i in reversed(xrange(n)):
            for j in xrange(i, n):
                if i == j:
                    dp[i][j] = True
                elif s[i] == s[j]:
                    dp[i][j] = dp[i+1][j-1] if i+1<=j-1 else True
                if dp[i][j] and j-i+1 > len(result):
                    result = s[i:j+1]
        return result