自己做的网站添加域名,大学网站建设的目标与思路,邯郸房产网安居客,重庆网站制作套餐115. 不同的子序列
给你两个字符串 s 和 t #xff0c;统计并返回在 s 的 子序列 中 t 出现的个数#xff0c;结果需要对 109 7 取模。 示例 1#xff1a;
输入#xff1a;s rabbbit, t rabbit
输出#xff1a;3
解释#xff1a;
如下所示,…115. 不同的子序列
给你两个字符串 s 和 t 统计并返回在 s 的 子序列 中 t 出现的个数结果需要对 109 7 取模。 示例 1
输入s rabbbit, t rabbit
输出3
解释
如下所示, 有 3 种可以从 s 中得到 rabbit 的方案。
rabbbit
rabbbit
rabbbit
示例 2
输入s babgbag, t bag
输出5
解释
如下所示, 有 5 种可以从 s 中得到 bag 的方案。
babgbag
babgbag
babgbag
babgbag
babgbagclass Solution:def numDistinct(self, s: str, t: str) - int:dp[[0 for i in range(len(t)1)] for i in range(len(s)1)]dp[0][0]1for i in range(1,len(t)1):dp[0][i]0for j in range(1,len(s)1):dp[j][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] #s[i-1]参与匹配s[i-1]不参与匹配else:dp[i][j]dp[i-1][j] #s[i-1]不参与匹配return dp[-1][-1]
583. 两个字符串的删除操作
给定两个单词 word1 和 word2 返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。 示例 1
输入: word1 sea, word2 eat
输出: 2
解释: 第一步将 sea 变为 ea 第二步将 eat 变为 ea示例 2:
输入word1 leetcode, word2 etco
输出4 class Solution:def minDistance(self, word1: str, word2: str) - int:dp[[0 for i in range(len(word1)1)] for j in range(len(word2)1)]dp[0][0]0for i in range(1,len(word1)1):dp[0][i]ifor j in range(1,len(word2)1):dp[j][0]jfor i in range(1,len(word2)1):for j in range(1,len(word1)1):if word2[i-1]word1[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]2) #三种删除方式return dp[-1][-1]
72. 编辑距离
给你两个单词 word1 和 word2 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作
插入一个字符删除一个字符替换一个字符 示例 1
输入word1 horse, word2 ros
输出3
解释
horse - rorse (将 h 替换为 r)
rorse - rose (删除 r)
rose - ros (删除 e)示例 2
输入word1 intention, word2 execution
输出5
解释
intention - inention (删除 t)
inention - enention (将 i 替换为 e)
enention - exention (将 n 替换为 x)
exention - exection (将 n 替换为 c)
exection - execution (插入 u) class Solution:def minDistance(self, word1: str, word2: str) - int:dp[[0 for i in range(len(word1)1)] for j in range(len(word2)1)]dp[0][0]0for i in range(1,len(word1)1):dp[0][i]ifor j in range(1,len(word2)1):dp[j][0]jfor i in range(1,len(word2)1):for j in range(1,len(word1)1):if word2[i-1]word1[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]
