Longest Palindrome Substring
题目描述
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.
解题方法
brute force
i,j 确定一个substring,然后再check这个substring是否是palindrome。
时间复杂度是O(n^2 * n) = O(n^3)
DP
在brute中有很多重复计算,并且两个palindrome之间是有关系的,所以很容易可以 往DP的方向想。
state
dp[i][j]
表示从i到j的substring是否为palindrome
function
if dp[j+1][i-1] == True and s[i] == s[j]:
dp[i][j] = True
这里要求j < i
并且dp[j+1][i-1]
在dp[j][i]
之前就已经计算出来了,所以
i应该从0到length的遍历,而j从0到i遍历,只有j == i - 1
的情况需要特殊处理,因为之前
的一个loop里j达不到这个i-1
.
- 时间复杂度
O(n^2)
- 空间复杂度
O(n^2)
确定pivot, 两边扩展
对于每个i,确定pivot向两边扩展找最大的palindrome
注意点
- palindrome长度可以是奇数也可以是偶数
- 奇数的话pivot就是
s[i]
偶数的话pivot就应该确定为
i-1
,i
的中间时间复杂度
O(n^2)
- 空间复杂度
O(1)
Solution
DP
方法正确,但是过不了test case, time limit exceeds
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if not s:
return ""
result = ""
length = len(s)
if length == 1:
return s
dp = [[False for i in range(length)] for j in range(length)]
for i in range(length):
dp[i][i] = True
if len(result) < 1:
result = s[i]
for i in range(length):
for j in range(i):
if j == i - 1:
if s[i] == s[j]:
dp[j][i] = True
if len(result) < 2:
result = s[j:i+1]
else:
if s[i] == s[j] and dp[j+1][i-1]:
dp[j][i] = True
if len(result) < i - j + 1:
result = s[j:i+1]
return result
确定中心往两边扩展
可以过test case
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if not s:
return ""
result = ""
length = len(s)
if length == 1:
return s
for i in range(1, length):
# center is between i - 1, i
# 长度为偶数的palindrome
low, high = i - 1, i
while low >= 0 and high < length and s[low] == s[high]:
low -= 1
high += 1
curLen = (high - 1) - (low + 1) + 1
if curLen > len(result):
result = s[low+1:high]
# center is i
# 长度为奇数的palindrome
low, high = i - 1, i + 1
while low >= 0 and high < length and s[low] == s[high]:
low -= 1
high += 1
curLen = (high - 1) - (low + 1) + 1
if curLen > len(result):
result = s[low+1:high]
return result