代码随想录算法训练营四十五天|115.不同的子序列、583.两个字符串的删除操作、72.编辑距离

本文主要是介绍代码随想录算法训练营四十五天|115.不同的子序列、583.两个字符串的删除操作、72.编辑距离，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：115. 不同的子序列 - 力扣（LeetCode）

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 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 dp[len(s)][len(t)]

题目链接：1143. 最长公共子序列 - 力扣（LeetCode）

思路：算出公共子序列的最大长度，那么用两个字符串的长度减去公共的部分，就得到了需要操作的最少步数

class Solution(object):def minDistance(self, word1, word2):""":type word1: str:type word2: str:rtype: int"""result = 0dp = [[0] * (len(word2) + 1) for _ in range(len(word1) + 1)]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] + 1else:dp[i][j] = max(dp[i-1][j], dp[i][j-1])result = dp[i][j] if dp[i][j] > result else dp[i][j]return len(word2) + len(word1) - 2 * result

题目链接：72. 编辑距离 - 力扣（LeetCode）

思路：思路跟之前求公共子序列差不多 分为dp[i-1] == dp[j-1] 的情况 和dp[i-1] != dp[j-1]的情况 不等于的情况下分为三种 1.修改一个字符 2.删除一个字符 3.添加一个字符 并取其中的最小值。

class Solution(object):def minDistance(self, word1, word2):""":type word1: str:type word2: str:rtype: int"""dp = [[0] * (len(word2) + 1) for _ in range(len(word1) + 1)]for i in range(len(word2) + 1):dp[0][i] = ifor i in range(len(word1) + 1):dp[i][0] = ifor 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(min(dp[i-1][j-1] + 1, dp[i-1][j] + 1), dp[i][j-1] + 1)return dp[len(word1)][len(word2)]

这篇关于代码随想录算法训练营四十五天|115.不同的子序列、583.两个字符串的删除操作、72.编辑距离的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---