Longest Palindromic Substring 解答

Question

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.

Solution

Palindrome类型的题目的关键都是这个递推表达式：

dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1]

逆向思维，于是我们想到由 dp[i][j] 可以推出以下：

dp[i - 1][j + 1], dp[i - 2][j + 2], dp[i - 3][j + 3]...

这题的一个思路是用DP构造2D Array，参见 Palindrome Subarray

另一个思路也是借助了DP的思想，时间复杂度仍是O(n²)，但是空间复杂度是O(1)

我们对于每个起点遍历，找以 1. 它为中心的最长对称子序列 2. （如果它和它的邻居相等）它和它的邻居为中心的最长对称子序列

代码如下

 1 class Solution(object):
 2     def spand(self, s, start, end):
 3         length = len(s)
 4         while start >= 0 and end < length:
 5             if s[start] == s[end]:
 6                 start -= 1
 7                 end += 1
 8             else:
 9                 break
10         return s[start + 1: end]
11     
12     def longestPalindrome(self, s):
13         """
14         :type s: str
15         :rtype: str
16         """
17         length = len(s)
18         result = s[0]
19         for i in range(length - 1):
20             # sub-length is odd 
21             result1 = self.spand(s, i, i)
22             if len(result) < len(result1):
23                 result = result1
24             # sub-length is even
25             if s[i] == s[i + 1]:
26                 result2 = self.spand(s, i, i + 1)
27                 if len(result) < len(result2):
28                     result = result2
29         return result