README
¶
编辑距离（Edit distance）
用动态规划的思想解决。
a = "horse" b = "ros"
| r | o | s | ||
|---|---|---|---|---|
| 0 | 1 | 2 | 3 | |
| h | 1 | 1 | 2 | 3 |
| o | 2 | 2 | 1 | 2 |
| r | 3 | 2 | 2 | 2 |
| s | 4 | 3 | 3 | 2 |
| e | 5 | 4 | 4 | 3 |
-
定义
d[i][j]d[i][j]代表a中前i个字符，变换到b中前j个字符，最短需要操作的次数- 需要考虑 a 或 b 一个字母都没有，即全增加/删除的情况，所以预留
d[0][j]和d[i][0]
-
状态转移
- 增：
d[i][j] = d[i][j - 1] + 1； - 删：
d[i][j] = d[i - 1][j] + 1； - 改：
d[i][j] = d[i - 1][j - 1] + 1； - 按顺序计算，当计算
d[i][j]时，d[i - 1][j]、d[i][j - 1]、d[i - 1][j - 1]均已经确定了； - 配合增删改这三种操作，需要对应的 d 把操作次数加一，取三种的最小；
- 如果刚好这两个字母相同
a[i - 1] = b[j - 1]，那么可以直接参考d[i - 1][j - 1]，操作不用加一。
- 增：
Documentation
¶
Overview ¶
* @lc app=leetcode id=72 lang=golang * * [72] Edit Distance * * https://leetcode.com/problems/edit-distance/description/ * * algorithms * Hard (41.17%) * Likes: 3296 * Dislikes: 50 * Total Accepted: 240.9K * Total Submissions: 570.7K * Testcase Example: '"horse"\n"ros"' * * Given two words word1 and word2, find the minimum number of operations * required to convert word1 to word2. * * You have the following 3 operations permitted on a word: * * * Insert a character * Delete a character * Replace a character * * * Example 1: * * * Input: word1 = "horse", word2 = "ros" * Output: 3 * Explanation: * horse -> rorse (replace 'h' with 'r') * rorse -> rose (remove 'r') * rose -> ros (remove 'e') * * * Example 2: * * * Input: word1 = "intention", word2 = "execution" * Output: 5 * Explanation: * intention -> inention (remove 't') * inention -> enention (replace 'i' with 'e') * enention -> exention (replace 'n' with 'x') * exention -> exection (replace 'n' with 'c') * exection -> execution (insert 'u') * *
Source Files