【Leetcode】72.编辑距离

KoreyLee 发布于2019-07-30 17:53 / 3099人阅读

摘要：题目给定两个单词和，计算出将转换成所使用的最少操作数。这个题目比较为主要是，状态转换比较复杂。

题目

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数。
你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例 1:

输入: word1 = "horse", word2 = "ros"
输出: 3
解释: 
horse -> rorse (将 "h" 替换为 "r")
rorse -> rose (删除 "r")
rose -> ros (删除 "e")

示例 2:

输入: word1 = "intention", word2 = "execution"
输出: 5
解释: 
intention -> inention (删除 "t")
inention -> enention (将 "i" 替换为 "e")
enention -> exention (将 "n" 替换为 "x")
exention -> exection (将 "n" 替换为 "c")
exection -> execution (插入 "u")

题解

这个题目拿到题目基本就能想到DP，因为感觉和我们之前的爬楼梯啥的比较相似。这个题目比较为hard主要是，状态转换比较复杂。

定义: dpi ， word1这个字符串的前i个 -> word1这个字符串的前j 个字符，所需要的最小的步数

那么有以下几种情况

word1[i] == word2[j]

不需要做变化，那么 dpi = dp[i-1,j-1]

word1[i] != word2[j]

我们就需要动用上面那三种操作了：

add = dp[i, j-1], 代表插入一个字符

delete = dp[i-1, j]，代表删除一个字符

replace = dp[i-1, j-1]，代表替换一个字符

dpi = 1 + min(add, delete, replace)

时间复杂度 o(m * n)

java

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        // base 
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }

        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (word1.charAt(i) == word2.charAt(j)) {
                    dp[i + 1][j + 1] = dp[i][j];
                } else {
                    int add = dp[i][j + 1];
                    int delete = dp[i + 1][j];
                    int rep = dp[i][j];
                    dp[i + 1][j + 1] = Math.min(Math.min(add, delete), rep) + 1;
                }
            }
        }
        return dp[m][n];
    }
}

python

class Solution:
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        m = len(word1)
        n = len(word2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m + 1):
            dp[i][0] = i
        for i in range(n + 1):
            dp[0][i] = i
        for i in range(m):
            for j in range(n):
                if word1[i] == word2[j]:
                    dp[i + 1][j + 1] = dp[i][j]
                else:
                    add = dp[i][j + 1]
                    delete = dp[i + 1][j]
                    replace = dp[i][j]
                    dp[i + 1][j + 1] = min(add, delete, replace) + 1
        return dp[m][n]

近期文章

【mysql】mysql系统架构

【Leetcode】71. 简化路径

【Leetcode】70. 爬楼梯

GPU云服务器云服务器编辑距离 LeetCode 72建站网 Discuz72

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/42478.html

【Leetcode】72.编辑距离

摘要：题目给定两个单词和，计算出将转换成所使用的最少操作数。这个题目比较为主要是，状态转换比较复杂。题目给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作：插入一个字符删除一个字符替换一个字符示例 1: 输入: word1 = horse, word2 = ros 输出: 3 解释: hor...

RaoMeng 2019-07-01 10:44 评论0 收藏0
【Leetcode】72.编辑距离

摘要：题目给定两个单词和，计算出将转换成所使用的最少操作数。这个题目比较为主要是，状态转换比较复杂。题目给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作：插入一个字符删除一个字符替换一个字符示例 1: 输入: word1 = horse, word2 = ros 输出: 3 解释: hor...

archieyang 2019-08-26 12:19 评论0 收藏0
【Leetcode】72.编辑距离

摘要：题目给定两个单词和，计算出将转换成所使用的最少操作数。这个题目比较为主要是，状态转换比较复杂。题目给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作：插入一个字符删除一个字符替换一个字符示例 1: 输入: word1 = horse, word2 = ros 输出: 3 解释: hor...

TZLLOG 2019-08-30 15:54 评论0 收藏0
力扣(LeetCode)72

摘要：题目地址题目描述给定两个单词和，计算出将转换成所使用的最少操作数。那么答案则为那么如何求呢也就是转移方程。由定义可以知道空字符串变成任意长度字符串的代价为该字符串的长度，也就是说。若，那么这里的解释是，增加了一个比较对象，变成。题目地址：https://leetcode-cn.com/probl...题目描述：给定两个单词 word1 和 word2，计算出将 word1 转换成 w...

tinysun1234 2019-08-16 15:08 评论0 收藏0
实现拼写检查器(spell check)

摘要：本文同时发在我的博客上，欢迎在百度或者搜索的时候，有时会小手一抖，打错了个别字母，比如我们想搜索，错打成了，但神奇的是，即使我们敲下回车，搜索引擎也会自动搜索而不是，这是怎么实现的呢本文就将从头实现一个版的拼写检查器基础理论首先，我们要确定本文同时发在我的github博客上，欢迎star 在百度或者Google搜索的时候，有时会小手一抖，打错了个别字母，比如我们想搜索apple，错打...

Harriet666 2019-08-23 15:35 评论0 收藏0