Posted on 2022-10-26 05:27
Uriel 阅读(42)
评论(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]