Leetcode 刷题笔记1 动态规划part13
leetcode 647 回文子串
暴力解法:
class Solution:
def countSubstrings(self, s: str) -> int:
ans = 0
for i in range(1, len(s) + 1):
for j in range(len(s) - i + 1):
if s[j:j + i] == s[j:j + i][::-1]:
ans +=1
return ans
dp:
class Solution:
def countSubstrings(self, s: str) -> int:
dp = [[False] * len(s) for _ in range(len(s))]
ans = 0
for i in range(len(s)-1, -1, -1):
for j in range(i, len(s)):
if s[i] == s[j] and (j - i <= 1 or dp[i + 1][j - 1]):
dp[i][j] = True
ans += 1
return ans
中心扩散法(双指针法):
class Solution:
def countSubstrings(self, s: str) -> int:
ans = 0
for i in range(len(s)):
ans += self.extend(s, i, i,len(s))
ans += self.extend(s, i, i+1,len(s))
return ans
def extend(self, s, i, j, n):
ans = 0
while i >= 0 and j < n and s[i] == s[j]:
i -= 1
j += 1
ans += 1
return ans
leetcode 516 最长回文子串
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
dp = [[0] * len(s) for i in range(len(s))]
for i in range(len(s)):
dp[i][i] = 1
for i in range(len(s)-1, -1, -1):
for j in range(i + 1, len(s)):
if s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
return dp[0][-1]
原文地址:https://blog.csdn.net/pinglejun/article/details/146251933
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/586040.html 如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/586040.html 如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!