【刷题DAY55】583, 72.md

发表于 | 分类于

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

题目链接：https://leetcode.cn/problems/delete-operation-for-two-strings/

0x1 看到题目的第一想法

0x2 自己实现过程中遇到哪些困难

0x3 今日学习的文章链接，或者视频链接

0x4 看完代码随想录之后的想法

  • 求两个字符串的最长公共子序列长度，用字符串长度减去最长公共子序列长度就是要删除的个数
  • 求两个字符串的最长公共子序列长度
  • dp[i][j] 以A[i-1]、B[j-1]结尾的字符串的最长公共子序列长度为dp[i][j]
  • if A[i-1] == B[j-1] dp[i][j] = dp[i-1][j-1] + 1
  • if A[i-1] != B[j-1] dp[i][j] = max(dp[i][j-1], dp[i-1][j])
  • dp = 0

0x5 今日收获，记录一下自己的学习时长

  • 1h

72. 编辑距离

题目链接：https://leetcode.cn/problems/edit-distance/

0x1 看到题目的第一想法

0x2 自己实现过程中遇到哪些困难

0x3 今日学习的文章链接，或者视频链接

0x4 看完代码随想录之后的想法

  • dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]
  • if (word1[i - 1] == word2[j - 1]) 那么说明不用任何编辑，dp[i][j] = dp[i - 1][j - 1]
  • if (word1[i - 1] != word2[j - 1]) 增删改
  • word1删除一个元素 dp[i][j] = dp[i - 1][j] + 1
  • word2删除一个元素 dp[i][j] = dp[i][j - 1] + 1
  • word2添加一个元素，相当于word1删除一个元素
  • 替换元素，word1替换word1[i - 1]，使其与word2[j - 1]相同，此时不用增删加元素。dp[i][j] = dp[i - 1][j - 1] + 1
  • dp[i][0] = i dp[0][j] = j

0x5 今日收获，记录一下自己的学习时长

  • 1.5h

总结

  • 两个字符串的删除操作
  • 编辑距离

复习

  • day32
    • 贪心
      • 买卖股票的最佳时机II
        • 所有的正区间之和
      • 跳跃游戏
        • 最大覆盖范围是否有终点
      • 跳跃游戏II
        • 下标到达当前最远覆盖范围都还没到终点，必须再走一步来增加覆盖范围 直到覆盖范围覆盖了终点

待重点复习

72, 45