Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
leetcode-dp
class Solution:
"""
PC: there might be multiple valid answer
<---i
s = "babad"
i
j
i從後面遍歷到前面, j從i遍歷到後面
dp[i][j]: longest palindromic for substring s[i:j]
"""
def longestPalindrome(self, s: str) -> str:
n = len(s)
if n == 1:
return s
dp = [[False for j in range(n)] for i in range(n)]
start, end = 0, 0
for i in range(n, -1, -1):
for j in range(i, n):
if j-i > 2:
if s[i]==s[j] and dp[i+1][j-1]:
dp[i][j] = True
if j-i > end-start:
start = i
end = j
else:
if s[i]==s[j]:
dp[i][j] = True
if j-i > end-start:
start = i
end = j
return s[start: end+1]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment