LeetCode：72. Edit Distance(编辑的最小步数)

「爱情、让人受尽委屈。」 2022-04-05 13:20 169阅读 0赞

> **文章最前**： 我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

**相关文章：**

1.  **[LeetCode：55. Jump Game（跳远比赛）][LeetCode_55. Jump Game]**
2.  **[Leetcode：300. Longest Increasing Subsequence（最大增长序列）][Leetcode_300. Longest Increasing Subsequence]**
3.  **[LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k][LeetCode_560. Subarray Sum Equals K_k])**

--------------------

**文件目录：**

题目描述：

java实现方法1：（利用动态规划）

python实现方式1:

源码github地址：https://github.com/zhangyu345293721/leetcode

--------------------

### 题目描述： ###

给定两个单词 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')

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/edit-distance

--------------------

### java实现方法1： ###

/**
         * 编辑距离最小步数
         *
         * @param word1 字符串1
         * @param word2 字符串2
         * @return 步数
         */
        public int minDistance(String word1, String word2) {
            int n = word1.length();
            int m = word2.length();
            if (n * m == 0){
                return n + m;
            }
            int[][] d = new int[n + 1][m + 1];
            for (int i = 0; i < n + 1; i++) {
                d[i][0] = i;
            }
            for (int j = 0; j < m + 1; j++) {
                d[0][j] = j;
            }
            for (int i = 1; i < n + 1; i++) {
                for (int j = 1; j < m + 1; j++) {
                    int left = d[i - 1][j] + 1;
                    int down = d[i][j - 1] + 1;
                    int leftDown = d[i - 1][j - 1];
                    if (word1.charAt(i - 1) != word2.charAt(j - 1)){
                        leftDown += 1;
                    }
                    d[i][j] = Math.min(left, Math.min(down, leftDown ));
                }
            }
            return d[n][m];
        }

时间复杂度：O(m.n)

空间复杂度：O(n)

--------------------

### python实现方式1: ###

import numpy as np
    
    
    def min_distance(word1: str, word2: str) -> int:
        '''
            得到最小步数
        Args:
            word1: 字符串1
            word2:字符串2
        Returns:
            最小步数
        '''
        m = len(word1)
        n = len(word2)
        if m * n == 0:
            return n + m
        d = np.zeros((m + 1, n + 1), dtype=np.int)
        for i in range(m + 1):
            d[i][0] = i
        for j in range(n + 1):
            d[0][j] = j
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                left = d[i - 1][j] + 1
                down = d[i][j - 1] + 1
                left_down = d[i - 1][j - 1]
                if word1[i - 1] != word2[j - 1]:
                    left_down += 1
                d[i][j] = min(left, min(down, left_down))
        return d[n][m]

时间复杂度：O(m.n)

空间复杂度：O(n)

--------------------

### 源码github地址： ###

[https://github.com/zhangyu345293721/leetcode][https_github.com_zhangyu345293721_leetcode]

[github]: https://github.com/zhangyu345293721
[LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870
[Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249
[LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201
[https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode