Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
求一个字符串中最长的回文子串,二维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]

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理