动态规划

字符串

  • 两个字符串最小的ASCII删除和

    难度：中等

    给定两个字符串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 的结果，比答案更大。

  • 方法一

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution:
      def minimumDeleteSum(self, s1: str, s2: str) -> int:
          m = len(s1)
          n = 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(mn)，其中 m 和 n 分别是字符串 s1和s2 的长度。二维数组 dp 有 m+1 行和 n+1 列，需要对 dp 中的每个元素进行计算。
    空间复杂度：O(mn)，其中 m 和 n 分别是字符串 s1和s2 的长度。创建了 m+1 行 n+1 列的二维数组 dp。