leetcode-200.最长回文子串

Posted on | In |

解题思路

由回文串正序和反序的性质相同，可以得出一个性质，如果一个字符串，其中心不是回文串，那么它一定不是个回文串。如果去掉头和尾，它依然还是一个回文串。在头和尾加上同一个字符也是一个回文串。

由此可以得出判断一个区间是否是回文串，可以由更小的区间得到，并且不受包含这个区间的大区间影响，所以满足无后效性且是最有子结构，可以用动态规划求解。

算法：动态规划
设dp(l, r)，代表区间[l, r]是否是回文串。

如果s[l] == s[r]，并且s[l + 1 ~ r - 1]是回文串的话，s[l ~ r]就是回文串。

复杂度分析
设字符串长度为n。

时间复杂度O(n^2)
枚举端点，O(1)时间转移，时间复杂度为O(n^2)。
空间复杂度O(n^2)
需要额外O(n^2)空间记录dp值。

代码

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
class Solution:
    """
    @param s: input string
    @return: the longest palindromic substring
    """
    def longestPalindrome(self, s):
        max_len=1
        # write your code here
        length=len(s)
        dp=[[0 for x in range(length)] for x in range(length)]
        for i in range(length):
            dp[i][i]=1
        for i in range(length-1):
            if s[i]==s[i+1]:
                dp[i][i+1]=1
                max_len=2
                start=2

        for new_len in range(3,length+1):
            for left in range(length-new_len+1):
                right=left+new_len-1
                if dp[left+1][right-1]==1 and s[left]==s[right]:
                    dp[left][right]=1
                    if new_len>max_len:
                        max_len=new_len
                        start=left
        return s[start:start+max_len]
s=Solution()
print(s.longestPalindrome("abcdzdcab"))

参考链接
https://www.jiuzhang.com/solutions/longest-palindromic-substring/#tag-highlight-lang-python