Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
求字符串的最长回文子序列,O(n^2) DP

 1 #516
 2 #Runtime: 953 ms (Beats 76.88%)
 3 #Memory: 28.6 MB (Beats 58.38%)
 4 
 5 class Solution(object):
 6     def longestPalindromeSubseq(self, s):
 7         """
 8         :type s: str
 9         :rtype: int
10         """
11         n = len(s)
12         dp = [[0] * n for _ in range(n)]
13         for i in range(n - 1, -1, -1):
14             dp[i][i] = 1
15             for j in range(i + 1, n):
16                 if s[i] == s[j]:
17                     dp[i][j] = dp[i + 1][j - 1] + 2
18                 else:
19                     dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
20         return dp[0][n-1]

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