day_45

本文主要是介绍day_45，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

115. 不同的子序列

class Solution:def numDistinct(self, s: str, t: str) -> int:dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]for i in range(len(s)):dp[i][0] = 1for j in range(1, len(t)):dp[0][j] = 0for 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[-1][-1]

583. 两个字符串的删除操作

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)):dp[i][0] = ifor j in range(len(word2)):dp[0][j] = jfor 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. 编辑距离

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] = ifor j in range(len(word2) + 1):dp[0][j] = jfor 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][j - 1] + 1, dp[i - 1][j] + 1, dp[i - 1][j - 1] + 1)return dp[-1][-1]

这篇关于day_45的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---