583 两个字符串的删除操作
二维dp数组表示使得0-i和0-j字符串相同所需的最少操作步数
通过算例分析dp数组的推导公式写出来了
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
dp = [[0]*(len(word2)+1) for _ in range(len(word1)+1)]
for i in range(len(word1)+1):
dp[i][0] = i
for i in range(len(word2)+1):
dp[0][i] = i
for i in range(1,len(word1)+1):
for j in range(1,len(word2)+1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1)
return dp[-1][-1]
看解答发现不相等时其实有三种情况,不过递推公式可简化为两种
72 编辑距离
dp数组表示0-i和0-j的字符串转换为相同所需最少步数
相同时还是步数不变
不同时的操作有三种
增加,删除,替换
增加和删除本质是一样的,和前面一致
替换有区别,替换可以直接修改dpi-1j-1,通过一次操作变成dpij
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
dp = [[0]*(len(word2)+1) for _ in range(len(word1)+1)]
for i in range(len(word1)+1):
dp[i][0] = i
for i in range(len(word2)+1):
dp[0][i] = i
for i in range(1,len(word1)+1):
for j in range(1,len(word2)+1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1)
return dp[-1][-1]
647 回文子串
好像可以暴力遍历?
必须On^2时间复杂度,估计会超时。。
直接使用切片判断,居然没超时
class Solution:
def countSubstrings(self, s: str) -> int:
res = 0
print(s[0:0])
for i in range(len(s)):
for j in range(i+1,len(s)+1):
if s[i:j] == s[i:j][::-1]:
res += 1
return res
再试试dp思路,
dp表示0-i字符串中回文子串的数目
递推?二维dp表示ij之间子串是否为回文子串,最后对dp数组求和
看了解答。发现dp数组定义没问题,不过循环和递推公式写不出来,并且暴力法实际上是On^3的,不过python利用切片一定程度上降低了复杂度,这可能是没有超时的原因
class Solution:
def countSubstrings(self, s: str) -> int:
dp = [[0]*len(s) for _ in range(len(s))]
res = 0
for i in range(len(s)-1,-1,-1):
for j in range(i,len(s)):
if s[i] == s[j]:
if j-i <= 1:
dp[i][j] = 1
res += 1
else:
if dp[i+1][j-1] == 1:
dp[i][j] = 1
res += 1
return res
关键在于遍历顺序和dp可以从哪个状态推导得到
516 最长回文子序列
按照前面一题的逻辑,只能找到最长回文子串,也就是说字串是连续的,但子序列并非如此
基本逻辑不变,如果ij字符相等,则判断中间是否回文,如果回文则延长后也是回文
但如果ij不相等,此时也有可能构成回文子序列,只要把ij都删掉即可?
不对,看了解答发现dp数组定义变了,直接定义为ij之间最长回文子序列长度即可,只要ij相等即可+2
还是没考虑全,当ij不相等的时候,得看把左边右边加上去,哪一边有更长的最长回文子序列,而不能粗暴地把ij两端都删掉
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
dp = [[0]*len(s) for _ in range(len(s))]
res = 1
for i in range(len(s)-1,-1,-1):
for j in range(i,len(s)):
if i == j:
dp[i][j] = 1
elif 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])
res = max(dp[i][j],res)
return res