动态规划16 | ● 583. 两个字符串的删除操作 ● *72. 编辑距离

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

https://programmercarl.com/0583.%E4%B8%A4%E4%B8%AA%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E5%88%A0%E9%99%A4%E6%93%8D%E4%BD%9C.html

• 考点
  • 子序列问题
• 我的思路
  • dp[i][j]的含义是，当两个字符串分别取前i和j个元素时，对应的最少相等删除步数是多少
  • 递推公式为，如果两个字符串第i和j个元素恰好相等，则dp值应等于不再考虑这两个元素的dp值即dp[i - 1][j - 1]；如果i和j不相等，则dp值应等于删除任一元素后的dp值取较小者即min(dp[i - 1][j] + 1, dp[i][j - 1] + 1)
  • 初始化，由于递推公式依赖于当前元素在二维矩阵中的左上元素，因此需要对二维矩阵的第一行和第一列进行初始化，初始化原则是，如果当前位置两字符串的元素相等，则dp等于将较长者除当前元素外其它元素均删除所需要的步数；如果不相等，dp等于不考虑较长字符串当前元素后所需要的最少步数和不考虑较短字符串当前元素（也就是令较短字符串为空）时所需要的最少步数中取较小者
• 视频讲解关键点总结
  • 和我的思路一致
• 我的思路的问题
  • 无
• 代码书写问题
  • 无
• 可执行代码

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [[0] * len(word2) for _ in range(len(word1))]
        if word1[0] == word2[0]:
            dp[0][0] = 0
        else:
            dp[0][0] = 2
        for i in range(1, len(word1)):
            if word1[i] == word2[0]:
                dp[i][0] = i
            else:
                dp[i][0] = min(dp[i - 1][0] + 1, i + 2)
        for i in range(1, len(word2)):
            if word1[0] == word2[i]:
                dp[0][i] = i
            else:
                dp[0][i] = min(dp[0][i - 1] + 1, i + 2)
        for i in range(1, len(word1)):
            for j in range(1, len(word2)):
                if word1[i] == word2[j]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1)
        return dp[-1][-1]

*72. 编辑距离

https://programmercarl.com/0072.%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB.html

• 考点
  • 子序列问题
• 我的思路
  • dp含义和上一题整体思路相同
  • 递推公式两元素相等的情况和上一题相同，但是两元素不相等的情况只考虑到了删除当前word1元素的解法
  • 初始化较为简单，不展开说了
• 视频讲解关键点总结
  • 我的思路的问题就在，递推公式里，如果两元素不相等，应该有三种处理方式（增、删、改），而我只实现了删的操作，其中增加一个元素也就是增加和word2当前元素相同的元素，也就是不需要考虑word2当前元素；删除也就是不考虑word1当前元素；改也就是不需要考虑word1和word2的当前元素
• 我的思路的问题
  • 漏了两种情况
• 代码书写问题
  • 无
• 可执行代码

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        if word1 == '' and word2 == '':
            return 0
        elif word1 == '':
            return len(word2)
        elif word2 == '':
            return len(word1)
        dp = [[0] * len(word2) for _ in range(len(word1))]
        if word1[0] == word2[0]:
            dp[0][0] = 0
        else:
            dp[0][0] = 1
        for i in range(1, len(word1)):
            if word1[i] == word2[0]:
                dp[i][0] = i
            else:
                dp[i][0] = dp[i - 1][0] + 1
        for i in range(1, len(word2)):
            if word1[0] == word2[i]:
                dp[0][i] = i
            else:
                dp[0][i] = dp[0][i - 1] + 1
        for i in range(1, len(word1)):
            for j in range(1, len(word2)):
                if word1[i] == word2[j]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(dp[i - 1][j] + 1, dp[i - 1][j - 1] + 1, dp[i][j - 1] + 1)
        return dp[-1][-1]

原文地址：https://blog.csdn.net/weixin_45055622/article/details/136994656

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！