Leetcode-刷题笔记1-动态规划part13
目录
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 ansdp：
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 ansleetcode 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]