要使两个字符串相等,需要删除其中某些字符。我们可以使用动态规划来解决这个问题。

首先,我们定义一个二维数组dp,其中dp[i][j]表示将字符串s1的前i个字符和字符串s2的前j个字符变为相等所需删除字符的ascll值的最小和。

接下来,我们可以考虑两种情况:

  1. 当s1[i-1] == s2[j-1]时,说明当前字符可以保留,不需要删除。因此,dp[i][j] = dp[i-1][j-1]。
  2. 当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 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录