Posted on 2022-10-26 05:27
Uriel 閱讀(50)
評論(0) 編輯 收藏 引用 所屬分類:
DP 、
閑來無事重切Leet Code
求一個字符串中最長的回文子串，二維dp，dp[i][j]標記下標從i到j的字符串是否為回文子串，注意兩重for循環的升序和降序順序，運行速度一般
1 #5
2 #Runtime: 7075 ms
3 #Memory Usage: 21.1 MB
4
5 class Solution(object):
6 def longestPalindrome(self, s):
7 """
8 :type s: str
9 :rtype: str
10 """
11 dp = [[0]*len(s) for i in range(len(s))]
12 l = len(s)
13 ans = 1
14 st_pos = 0
15 for j in range(l):
16 dp[j][j] = 1
17 for i in range(j - 1, -1, -1):
18 if s[i] == s[j]:
19 if j == i + 1:
20 dp[i][j] = 1
21 if j - i + 1 > ans:
22 ans = j - i + 1
23 st_pos = i
24 continue
25 if dp[i + 1][j - 1] == 1:
26 dp[i][j] = 1
27 if j - i + 1 > ans:
28 ans = j - i + 1
29 st_pos = i
30
31 return s[st_pos:st_pos + ans]