西安庆典公司_怎么去做推广_seo独立站_seo搜索引擎优化业务

给定两个单词 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:"""# 1.递归def dfs(i, j):if i < 0:return j + 1if j < 0:return i + 1if word1[i] == word2[j]:return dfs(i - 1, j - 1)return min(dfs(i, j - 1), dfs(i - 1, j)) + 1return dfs(len(word1) - 1, len(word2) - 1)""""""# 2.记忆化搜索cache = [[-1 for _ in range(len(word2))] for _ in range(len(word1))]def dfs(i, j):if i < 0:return j + 1if j < 0:return i + 1if cache[i][j] != -1:return cache[i][j]if word1[i] == word2[j]:res = dfs(i - 1, j - 1)cache[i][j] = resreturn resres = min(dfs(i, j - 1), dfs(i - 1, j)) + 1cache[i][j] = resreturn resreturn dfs(len(word1) - 1, len(word2) - 1)"""# 3.递推dp = [[0 for _ in range(len(word2) + 1)] for _ in range(len(word1) + 1)]dp[0] = [i for i in range(len(word2) + 1)]for i, x in enumerate(word1):dp[i + 1][0] = i + 1for j, y in enumerate(word2):if x == y:dp[i + 1][j + 1] = dp[i][j]else:dp[i + 1][j + 1] = min(dp[i + 1][j], dp[i][j + 1]) + 1return dp[-1][-1]

给定两个字符串s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。

示例 1:

输入: s1 = "sea", s2 = "eat"
输出: 231
解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。
在 "eat" 中删除 "t" 并将 116 加入总和。
结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。

示例 2:

输入: s1 = "delete", s2 = "leet"
输出: 403
解释: 在 "delete" 中删除 "dee" 字符串变成 "let"，
将 100[d]+101[e]+101[e] 加入总和。在 "leet" 中删除 "e" 将 101[e] 加入总和。
结束时，两个字符串都等于 "let"，结果即为 100+101+101+101 = 403 。
如果改为将两个字符串转换为 "lee" 或 "eet"，我们会得到 433 或 417 的结果，比答案更大。

class Solution:def minimumDeleteSum(self, s1: str, s2: str) -> int:"""# 1.递归def dfs(i, j):if i < 0:return sum([ord(s2[x]) for x in range(j+1)])if j < 0:return sum([ord(s1[x]) for x in range(i+1)])if s1[i] == s2[j]:return dfs(i - 1, j - 1)return min(dfs(i - 1, j) + ord(s1[i]), dfs(i, j - 1) + ord(s2[j]))return dfs(len(s1) - 1, len(s2) - 1)""""""# 2.记忆化搜索cache = [[-1 for _ in range(len(s2))] for _ in range(len(s1))]def dfs(i, j):if i < 0:return sum([ord(s2[x]) for x in range(j + 1)])if j < 0:return sum([ord(s1[x]) for x in range(i + 1)])if cache[i][j] != -1:return cache[i][j]if s1[i] == s2[j]:res = dfs(i - 1, j - 1)cache[i][j] = resreturn resres = min(dfs(i - 1, j) + ord(s1[i]), dfs(i, j - 1) + ord(s2[j]))cache[i][j] = resreturn resreturn dfs(len(s1) - 1, len(s2) - 1)"""# 3.递推dp = [[0 for _ in range(len(s2) + 1)] for _ in range(len(s1) + 1)]for i in range(1, len(s2) + 1):  # 当s1为空字符串时，删除s2所需要的值dp[0][i] = dp[0][i - 1] + ord(s2[i - 1])for i, x in enumerate(s1):dp[i + 1][0] = dp[i][0] + ord(s1[i])  # s2为空字符串时，删除s1所需要的值for j, y in enumerate(s2):if x == y:dp[i + 1][j + 1] = dp[i][j]else:dp[i + 1][j + 1] = min(dp[i][j + 1] + ord(x), dp[i + 1][j] + ord(y))return dp[-1][-1]

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。

两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 ：

• s = s1 + s2 + ... + sn
• t = t1 + t2 + ... + tm
• |n - m| <= 1
• 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...

注意：a + b 意味着字符串 a 和 b 连接。

示例 1：

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出：true

示例 2：

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出：false

示例 3：

输入：s1 = "", s2 = "", s3 = ""
输出：true

class Solution:def isInterleave(self, s1: str, s2: str, s3: str) -> bool:if len(s1) + len(s2) != len(s3):return False# 如果s1的最后一个字符下标为i，s2的最后一个字符下标为j，那么s3的最后一个字符下标为i+j+1# 如果s3的最后一个字符是s1的最后一个字符或者是s2的最后一个字符，问题就变成s1[i-1],s2[j]或s1[i],s2[j-1] 与s3[i+j]的子问题"""# 1.递归def dfs(i, j):if i == -1 and j == -1:return Trueif i < 0:return s2[: j + 1] == s3[: j + 1]if j < 0:return s1[: i + 1] == s3[: i + 1]return s3[i + j + 1] == s1[i] and dfs(i - 1, j) or s3[i + j + 1] == s2[j] and dfs(i, j - 1)return dfs(len(s1) - 1, len(s2) - 1)""""""# 2.记忆化搜索cache = [[-1 for _ in range(len(s2))] for _ in range(len(s1))]def dfs(i, j):if i == -1 and j == -1:return Trueif i < 0:return s2[: j + 1] == s3[: j + 1]if j < 0:return s1[: i + 1] == s3[: i + 1]if cache[i][j] != -1:return cache[i][j]res = s3[i + j + 1] == s1[i] and dfs(i - 1, j) or s3[i + j + 1] == s2[j] and dfs(i, j - 1)cache[i][j] = resreturn resreturn dfs(len(s1) - 1, len(s2) - 1)"""# 3.递推dp = [[0 for _ in range(len(s2) + 1)] for _ in range(len(s1) + 1)]dp[0][0] = Truefor i in range(1, len(s2) + 1):dp[0][i] = s2[:i] == s3[:i]for i, x in enumerate(s1):dp[i + 1][0] = s1[: i + 1] == s3[: i + 1]for j, y in enumerate(s2):dp[i + 1][j + 1] = (s3[i + j + 1] == s1[i]and dp[i][j + 1]or s3[i + j + 1] == s2[j]and dp[i + 1][j])return dp[-1][-1]

给你两个数组 nums1 和 nums2 。

请你返回 nums1 和 nums2 中两个长度相同的 非空 子序列的最大点积。

数组的非空子序列是通过删除原数组中某些元素（可能一个也不删除）后剩余数字组成的序列，但不能改变数字间相对顺序。比方说，[2,3,5] 是 [1,2,3,4,5] 的一个子序列而 [1,5,3] 不是。

示例 1：

输入：nums1 = [2,1,-2,5], nums2 = [3,0,-6]
输出：18
解释：从 nums1 中得到子序列 [2,-2] ，从 nums2 中得到子序列 [3,-6] 。
它们的点积为 (2*3 + (-2)*(-6)) = 18 。

示例 2：

输入：nums1 = [3,-2], nums2 = [2,-6,7]
输出：21
解释：从 nums1 中得到子序列 [3] ，从 nums2 中得到子序列 [7] 。
它们的点积为 (3*7) = 21 。

示例 3：

输入：nums1 = [-1,-1], nums2 = [1,1]
输出：-1
解释：从 nums1 中得到子序列 [-1] ，从 nums2 中得到子序列 [1] 。
它们的点积为 -1 。

class Solution:def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:"""# 1.递归def dfs(i, j):if i < 0 or j < 0:# 返回负无穷大而不是0，因为数组中的点积相乘有可能有负数，这时候应该返回的是负数，而不是0return -infreturn max(nums1[i] * nums2[j],    # 选择当前元素，前面的都舍弃，因为前面的结果有可能是负数nums1[i] * nums2[j] + dfs(i - 1, j - 1),    # 选择当前元素加上前面的结果dfs(i - 1, j),dfs(i, j - 1),)return dfs(len(nums1) - 1, len(nums2) - 1)""""""# 2.记忆化搜索cache = [[-100001 for _ in range(len(nums2))] for _ in range(len(nums1))]def dfs(i, j):if i < 0 or j < 0:return -infif cache[i][j] != -100001:return cache[i][j]res = max(nums1[i] * nums2[j],nums1[i] * nums2[j] + dfs(i - 1, j - 1),dfs(i - 1, j),dfs(i, j - 1),)cache[i][j] = resreturn resreturn dfs(len(nums1) - 1, len(nums2) - 1)"""# 3.递推dp = [[float("-inf") for _ in range(len(nums2) + 1)] for _ in range(len(nums1) + 1)]for i, x in enumerate(nums1):for j, y in enumerate(nums2):dp[i + 1][j + 1] = max(x * y, x * y + dp[i][j], dp[i][j + 1], dp[i + 1][j])return dp[-1][-1]

给你两个字符串 str1 和 str2，返回同时以 str1 和 str2 作为 子序列 的最短字符串。如果答案不止一个，则可以返回满足条件的 任意一个 答案。

如果从字符串 t 中删除一些字符（也可能不删除），可以得到字符串 s ，那么 s 就是 t 的一个子序列。

示例 1：

输入：str1 = "abac", str2 = "cab"
输出："cabac"
解释：
str1 = "abac" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 的第一个 "c"得到 "abac"。 
str2 = "cab" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 末尾的 "ac" 得到 "cab"。
最终我们给出的答案是满足上述属性的最短字符串。

示例 2：

输入：str1 = "aaaaaaaa", str2 = "aaaaaaaa"
输出："aaaaaaaa"

class Solution:def shortestCommonSupersequence(self, str1: str, str2: str) -> str:# 观察示例1，结果字符串的最后一个字符是str1的最后一个字符，删除结果字符串和str1的最后一个字符# 此时结果字符串的最后一个字符是str1的最后一个字符，依旧删除# 现在结果字符串的最后一个字符与str1与str2的最后一个字符都相同，三个字符串一起删除最后一个字符# 将结果字符串和str1的最后一个相同字符删除# 此时str1为空，将剩余的str2加入结果字符串"""# 1.递归def dfs(i, j):if i < 0:return str2[: j + 1]if j < 0:return str1[: i + 1]if str1[i] == str2[j]:return dfs(i - 1, j - 1) + str1[i]else:if len(dfs(i - 1, j)) < len(dfs(i, j - 1)):return dfs(i - 1, j) + str1[i]else:return dfs(i, j - 1) + str2[j]return dfs(len(str1) - 1, len(str2) - 1)""""""# 2.记忆化搜索cache = [[-1 for _ in range(len(str2))] for _ in range(len(str1))]def dfs(i, j):if i < 0:return str2[: j + 1]if j < 0:return str1[: i + 1]if cache[i][j] != -1:return cache[i][j]if str1[i] == str2[j]:res = dfs(i - 1, j - 1) + str1[i]cache[i][j] = resreturn reselse:res = dfs(i - 1, j) + str1[i] if len(dfs(i - 1, j)) < len(dfs(i, j - 1)) else dfs(i, j - 1) + str2[j]cache[i][j] = resreturn resreturn dfs(len(str1) - 1, len(str2) - 1)"""# 3.递推dp = [[0 for _ in range(len(str2) + 1)] for _ in range(len(str1) + 1)]dp[0] = [str2[:i] for i in range(len(str2) + 1)]for i, x in enumerate(str1):dp[i + 1][0] = str1[: i + 1]for j, y in enumerate(str2):if x == y:dp[i + 1][j + 1] = dp[i][j] + str1[i]else:if len(dp[i + 1][j]) > len(dp[i][j + 1]):dp[i + 1][j + 1] = dp[i][j + 1] + str1[i]else:dp[i + 1][j + 1] = dp[i + 1][j] + str2[j]return dp[-1][-1]