115. 不同的子序列
本题是在原来匹配子序列的基础上增加了统计所匹配的子序列个数,也就是dp数组的定义和更新公式和原来的有所区别。
1、dp数组的定义
dp[i][j]表示以i-1和j-1为末尾的字符串中,给定字符串s包含目标字符串t的个数。注意这里不是长度。
2、dp数组的更新
(1)当前字符相等,分两种情况:
1.1、不包含当前t[j-1]和s[i-1]字符时,所能够存在的数量dp[i-1][j-1];
1.2、包含当前t[i-1]字符时,但是不包含s[i-1]字符的时候,所能达到的数量(也就是给定字符串还没有走到i-1位置,但是已经包含j-1位置的t的个数)。
dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
(2)当前字符不相等的时候,只能保留1.2描述的内容。
dp[i]][j] = dp[i-1][j];
3、dp数组初始化
分开行和列来看,dp[i][0]表示目标串是空字符串,也就是给定字符串删除全部元素即可,所以全是1;dp[0][j]表示给定字符串是空字符的时候,这时候目标字符串找不到匹配的,所以全是0.
注意,这里需要考虑0,0的情况,也就是空字符串匹配空字符串,结果是1,所以dp[0][0] = 1。
4、确定遍历顺序
本题遍历顺序是按照子串匹配的顺序遍历。外层for循环走给定字符串s(较长的),内层for循环走目标字符串t(较短的)。
class Solution(object):def numDistinct(self, s, t):""":type s: str:type t: str:rtype: int"""dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]for j in range(len(t) + 1):dp[0][j] = 0for i in range(len(s) + 1):dp[i][0] = 1for i in range(1, len(s) + 1):for j in range(1, len(t) + 1):if s[i-1] == t[j-1]:dp[i][j] = dp[i-1][j-1] + dp[i-1][j]else:dp[i][j] = dp[i-1][j]# return int(dp[-1][-1] % (1e10+7))return dp[-1][-1]
583. 两个字符串的删除操作
解法一:所需的步数也就是两个字符串分别达到“最大公共子串”所需要的步数。
1、先求出“不连续”包含的最大子串的长度;
2、返回两个字符串的长度和-2*最大子串长度。
OMG活学活用!
class Solution(object):def minDistance(self, word1, word2):""":type word1: str:type word2: str:rtype: int"""len_1 = len(word1)len_2 = len(word2)dp = [[0] * (len_2+ 1) for _ in range(len_1 + 1)]for i in range(1, len_1+1):for j in range(1, len_2+1):if word1[i-1] == word2[j-1]:dp[i][j] = dp[i-1][j-1] + 1else:dp[i][j] = max(dp[i-1][j], dp[i][j-1])return len_1 + len_2 - dp[-1][-1] * 2 # 最后返回的值就是两个字符串分别达到“最大公共子串”需要删除的字符个数
解法二:直接用dp指示当前的位置处匹配所需要的最少的步数。
1、dp数组的定义
dp[i][j]表示i-1和j-1位值处的word1和word2,能够匹配到最长字符串所需要删除的字符个数;
2、dp更新
(1)当前字符相等,则保持不变:dp[i][j] = dp[i-1][j-1];
(2)当前字符不相等,则由之前的dp进行推算。这里依然是取两个值,一个是hold word1当前字符,删除word2中的,一个是hold word2中的字符,删除word1的。取最小值然后+1即可。
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1;
3、初始化
初始化比较刁钻。
需要反向来思考:对于其中一个是空字符串,index = 0,那么此时若需要匹配,则需要另一个字符串在相应的位置删除全部的元素。所以需要两个for来初始化i,j = 0的行列。
for i in range(len_1+1):dp[i][0] = ifor j in range(len_2+1):dp[0][j] = j
4、确定遍历顺序
本质还是字符串匹配的遍历,两层for从小到大遍历。
class Solution(object):def minDistance(self, word1, word2):""":type word1: str:type word2: str:rtype: int"""len_1 = len(word1)len_2 = len(word2)# 解法二dp = [[0] * (len_2 + 1) for _ in range(len_1 + 1)]for i in range(len_1+1):dp[i][0] = ifor j in range(len_2+1):dp[0][j] = jfor i in range(1, len_1+1):for j in range(1, len_2+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], dp[i][j-1]) + 1return dp[-1][-1]
本题的解法1更加推荐,因为和之前“不连续”最大公共子串可以直接复用,实现也比较简单,也不需要控制边界情况或者考虑初始化细节。
72. 编辑距离
本题是前几个编辑距离的扩充版,考虑了“非连续”“增删换”等不同的操作以及操作之间的合并。
1、确定dp数组含义
dp[i][j]表示在i-1、j-1位置处,word1和word2能够达到最小修改步骤的值;
2、确定dp数组的更新公式
(1)当前字符相等,那么无需步骤来修改,hold上一个匹配的dp值即可:dp[i][j] = dp[i-1][j-1];
(2)当前字符不匹配,则需要逐一讨论“增、删、换”三种操作的表达式,最后取最小值+1即可:
2.1删
删除和之前的表达式完全一致,分别hold住两个word当前位置的index,另一个往前回退一个,也就是dp[i-1][j] + 1和dp[i][j] + 1。
2.2增
增加和删除其实是相同的操作,因为在此字符串位置增加,就相当于在另一个字符的位置删掉一个,所以可以和上面的表达式合并。比如“abc”和“ab”在c位置处,可以选择增加一个c在word2,也可以选择在word1删除一个c,两个操作实际上都是在hold住一个,另一个回退的基础上进行更新的。
2.3换
换操作相当于在现在位置上的字符更新为相同值。不妨反过来想:如果当前字符匹配,则hold住两个字符串上一个index所对应的dp的值,那么现在换了一个元素相当于在相等前,增加了一个步骤,所以dp[i][j] = 1+dp[i-1][j-1]。
3、确定初始化
本题和上一题的初始化相同,因为都涉及对于0行、0列元素的调用,具体的初始化是两个for分别遍历整个0行和0列,dp等于对应的index值。
4、确定遍历顺序
由于dp是分别由前一行、前一列推到而来,所以遍历顺序是从小到大,内外两个for循环。
class Solution(object):def minDistance(self, word1, word2):""":type word1: str:type word2: str:rtype: int"""len_1 = len(word1)len_2 = len(word2)dp = [[0] * (len_2 + 1) for _ in range(len_1 + 1)]for i in range(len_1+1): dp[i][0] = ifor j in range(len_2+1): dp[0][j] = jfor i in range(1, len_1 + 1):for j in range(1, len_2 + 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], dp[i][j-1], dp[i-1][j-1]) + 1 # 合并后的表达式return dp[-1][-1]
Day51完结!!!