LeetCode072:编辑距离

た入场券 2022-05-18 03:56 196阅读 0赞

**实验平台**：[LeetCode][]  
**代码地址**：[my github][]

### 题目描述： ###

![这里写图片描述][70]

### 示例： ###

![这里写图片描述][70 1]

### 运行结果： ###

![这里写图片描述][70 2]

### 代码： ###

class Solution {
        public int minDistance(String word1, String word2) {
            char[] a = word1.toCharArray();
            char[] b = word2.toCharArray();
            int[][] times = new int[a.length + 1][b.length + 1];
    
            for (int i = 0; i <= a.length; i++) {
                times[i][0] = i;
            }
            for (int j = 0; j <= b.length; j++) {
                times[0][j] = j;
            }
    
            for (int i = 1; i <= a.length; i++) {
                for (int j = 1; j <= b.length; j++) {
    
                    if (a[i - 1] == b[j - 1]) {
                        times[i][j] = times[i - 1][j - 1];
                    } else {
                        times[i][j] = Math.min(times[i - 1][j - 1] + 1, Math.min(times[i][j - 1] + 1, times[i - 1][j] + 1));
                    }
                }
            }
            return times[a.length][b.length];
        }
    }

[LeetCode]: https://leetcode-cn.com/problemset/all/
[my github]: https://github.com/TimePickerWang/LeetCode
[70]: /images/20220518/6d0319256c914ea9abc298f320e1d05f.png
[70 1]: /images/20220518/d7ba5894137840a4b30efc54d6864eef.png
[70 2]: /images/20220518/9aaccdcf257c47119488f17bdc6bdae7.png

发表评论取消回复

表情：

评论列表（有 0 条评论，196人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode-72. 编辑距离

目录动态规划题目来源 [72. 编辑距离][72.] 动态规划 1.确定dp数组（dp table）以及下标的含义 dp\[i\]\[j\

红太狼/ 2024年03月24日 12:49/ 0 赞/ 57 阅读

相关 leetcode 编辑距离动态规划

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

「爱情、让人受尽委屈。」/ 2023年08月17日 15:43/ 0 赞/ 216 阅读

相关 leetcode 72. 编辑距离

思路： dp\[i\]\[j\]表示以word1\[i\]结尾的字符串，变为以word2\[j\]结尾的字符，需要的最少编辑次数。若word1\[i\]==word2\[

雨点打透心脏的1/2处/ 2023年07月03日 02:47/ 0 赞/ 15 阅读

相关 leetcode72 编辑距离

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

淩亂°似流年/ 2023年06月20日 06:18/ 0 赞/ 28 阅读

相关 leetcode72 编辑距离

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

阳光穿透心脏的1/2处/ 2023年06月16日 10:47/ 0 赞/ 138 阅读

相关 Leetcode 72. 编辑距离

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

叁歲伎倆/ 2022年09月02日 13:55/ 0 赞/ 168 阅读

相关 LeetCode072:编辑距离

实验平台：[LeetCode][] 代码地址：[my github][] 题目描述： ![这里写图片描述][70] 示例： ![这里写图片描述][70 1]

た入场券/ 2022年05月18日 03:56/ 0 赞/ 197 阅读

相关 LeetCode 72.Edit Distance (编辑距离)

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

墨蓝/ 2022年04月15日 04:30/ 0 赞/ 247 阅读

相关【leetcode】编辑距离（动态规划）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

旧城等待，/ 2022年02月27日 04:16/ 0 赞/ 301 阅读

相关 leetcode 72. 编辑距离

![1588437-20190516145616651-338815526.png][] / 定义状态： DP[i][j]其中i表示word1前i个字

悠悠/ 2021年12月21日 01:27/ 0 赞/ 380 阅读