给定两个字符串s1和s2返回使两个字符串相等所需删除字符的ascll值的最小和
要使两个字符串相等,需要删除其中某些字符。我们可以使用动态规划来解决这个问题。
首先,我们定义一个二维数组dp,其中dp[i][j]表示将字符串s1的前i个字符和字符串s2的前j个字符变为相等所需删除字符的ascll值的最小和。
接下来,我们可以考虑两种情况:
- 当s1[i-1] == s2[j-1]时,说明当前字符可以保留,不需要删除。因此,dp[i][j] = dp[i-1][j-1]。
- 当s1[i-1] != s2[j-1]时,说明当前字符需要删除。我们可以选择删除s1[i-1]或者s2[j-1],取删除后ascll值最小的那个字符。因此,dp[i][j] = min(dp[i-1][j] + ord(s1[i-1]), dp[i][j-1] + ord(s2[j-1]))。
最后,dp[len(s1)][len(s2)]即为所求的最小和。
具体的代码实现如下:
def minimumDeleteSum(s1: str, s2: str) -> int:
m, n = len(s1), len(s2)
dp = [[0] * (n+1) for _ in range(m+1)]
for i in range(1, m+1):
dp[i][0] = dp[i-1][0] + ord(s1[i-1])
for j in range(1, n+1):
dp[0][j] = dp[0][j-1] + ord(s2[j-1])
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(dp[i-1][j] + ord(s1[i-1]), dp[i][j-1] + ord(s2[j-1]))
return dp[m][n]
时间复杂度分析:动态规划的状态转移需要遍历所有的字符,所以时间复杂度为O(m*n),其中m和n分别为s1和s2的长度。
空间复杂度分析:我们使用了一个二维数组来保存状态,所以空间复杂度为O(m*n)
原文地址: https://www.cveoy.top/t/topic/iSiN 著作权归作者所有。请勿转载和采集!