72. 編輯距離：
給你兩個單詞 word1 和 word2， 請返回將 word1 轉(zhuǎn)換成 word2 所使用的最少操作數(shù) 。
你可以對一個單詞進(jìn)行如下三種操作：
- 插入一個字符
- 刪除一個字符
- 替換一個字符
樣例 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')
提示：
0 <= word1.length, word2.length <= 500-
word1和word2由小寫英文字母組成
分析：
-
面對這道算法題目，二當(dāng)家的再次陷入了沉思。
-
編輯距離算法在實(shí)際應(yīng)用中還是很多的，比如一些命令的參數(shù)，當(dāng)輸入了錯誤的參數(shù)時，會提示最相似的命令。
- 想要找最優(yōu)解，一般就是貪心或者動態(tài)規(guī)劃。 -
思考后會發(fā)現(xiàn)，完整串的編輯距離和子串的編輯距離有關(guān)系，所以考慮使用動態(tài)規(guī)劃。
-
別急，這里還有一個問題，題目中可以對兩個單詞分別進(jìn)行三種操作，所以相當(dāng)于一共有六種操作，其中插入字符依賴較短字符串，而刪除字符的操作就反向依賴了較長串，但是動態(tài)規(guī)劃是從一個初識條件開始，朝著一個方向計算的，這里依賴著兩種方向，這怎么辦？
-
其實(shí)，我們可以將相同效果的操作合并處理：
-
對單詞 A 刪除一個字符和對單詞 B 插入一個字符是等價的。例如當(dāng)單詞 A 為 doge，單詞 B 為 dog 時，我們既可以刪除單詞 A 的最后一個字符 e，得到相同的 dog，也可以在單詞 B 末尾添加一個字符 e，得到相同的 doge；
-
同理，對單詞 B 刪除一個字符和對單詞 A 插入一個字符也是等價的；
-
對單詞 A 替換一個字符和對單詞 B 替換一個字符是等價的。例如當(dāng)單詞 A 為 bat，單詞 B 為 cat 時，我們修改單詞 A 的第一個字母 b -> c，和修改單詞 B 的第一個字母 c -> b 是等價的。
-
-
這樣一來，本質(zhì)不同的操作實(shí)際上只有三種：
-
在單詞 A 中插入一個字符；
-
在單詞 B 中插入一個字符；
-
修改單詞 A 的一個字符。
-
-
這樣一來，我們就可以把原問題轉(zhuǎn)化為規(guī)模較小的子問題。以樣例1為例，我們用 A = horse，B = ros 作為例子，來看一看是如何把這個問題轉(zhuǎn)化為規(guī)模較小的若干子問題的：
-
在單詞 A 中插入一個字符：如果我們知道 horse 到 ro 的編輯距離為 a，那么顯然 horse 到 ros 的編輯距離不會超過 a + 1。這是因?yàn)槲覀兛梢栽?a 次操作后將 horse 和 ro 變?yōu)橄嗤淖址?，只需要額外的 1 次操作，在單詞 A 的末尾添加字符 s，就能在 a + 1 次操作后將 horse 和 ro 變?yōu)橄嗤淖址?/p>
-
在單詞 B 中插入一個字符：如果我們知道 hors 到 ros 的編輯距離為 b，那么顯然 horse 到 ros 的編輯距離不會超過 b + 1，原因同上；
-
修改單詞 A 的一個字符：如果我們知道 hors 到 ro 的編輯距離為 c，那么顯然 horse 到 ros 的編輯距離不會超過 c + 1，原因同上。
-
-
那么從 horse 變成 ros 的編輯距離應(yīng)該為 min(a + 1, b + 1, c + 1)。
-
因此，我們就可以使用動態(tài)規(guī)劃來解決這個問題了。我們用 D[i][j] 表示 A 的前 i 個字母和 B 的前 j 個字母之間的編輯距離。
-
如上所述，當(dāng)我們獲得 D[i][j-1]，D[i-1][j] 和 D[i-1][j-1] 的值之后就可以計算出 D[i][j]。
-
D[i][j-1] 為 A 的前 i 個字符和 B 的前 j - 1 個字符編輯距離的子問題。即對于 B 的第 j 個字符，我們在 A 的末尾添加了一個相同的字符，那么 D[i][j] 最小可以為 D[i][j-1] + 1；
-
D[i-1][j] 為 A 的前 i - 1 個字符和 B 的前 j 個字符編輯距離的子問題。即對于 A 的第 i 個字符，我們在 B 的末尾添加了一個相同的字符，那么 D[i][j] 最小可以為 D[i-1][j] + 1；
-
D[i-1][j-1] 為 A 前 i - 1 個字符和 B 的前 j - 1 個字符編輯距離的子問題。即對于 B 的第 j 個字符，我們修改 A 的第 i 個字符使它們相同，那么 D[i][j] 最小可以為 D[i-1][j-1] + 1。特別地，如果 A 的第 i 個字符和 B 的第 j 個字符原本就相同，那么我們實(shí)際上不需要進(jìn)行修改操作。在這種情況下，D[i][j] 最小可以為 D[i-1][j-1]。
-
-
一般題解到這里就結(jié)束了，但其實(shí)我們還可以繼續(xù)優(yōu)化空間。
-
由于動態(tài)規(guī)劃中，我們比較兩個子串，只依賴于各減少最后一個字符的子串的編輯距離，所以我們的動態(tài)規(guī)劃數(shù)組是可以重復(fù)利用的，不需要二維數(shù)組，只需要一維數(shù)組即可，即滾動數(shù)組的方式。文章來源：http://www.zghlxwxcb.cn/news/detail-662050.html
題解：
rust：
二維數(shù)組（易懂）
impl Solution {
pub fn min_distance(word1: String, word2: String) -> i32 {
let l1 = word1.len();
let l2 = word2.len();
// 有一個字符串為空串
if l1 == 0 || l2 == 0 {
return (l1 + l2) as i32;
}
// DP 數(shù)組
let mut dp = vec![vec![0; l2 + 1]; l1 + 1];
// 邊界狀態(tài)初始化
(0..=l1).for_each(|i| {
dp[i][0] = i;
});
(0..=l2).for_each(|i| {
dp[0][i] = i;
});
// 計算所有 DP 值
(1..=l1).for_each(|i| {
(1..=l2).for_each(|j| {
let insert1 = dp[i - 1][j] + 1;
let insert2 = dp[i][j - 1] + 1;
let replace1 = if word1.as_bytes()[i - 1] != word2.as_bytes()[j - 1] {
dp[i - 1][j - 1] + 1
} else {
// 兩個字母相同，不用修改，所以操作次數(shù)不變
dp[i - 1][j - 1]
};
dp[i][j] = insert1.min(insert2).min(replace1);
});
});
return dp[l1][l2] as i32;
}
}
滾動數(shù)組（更加優(yōu)化的內(nèi)存空間）
impl Solution {
pub fn min_distance(mut word1: String, mut word2: String) -> i32 {
let mut l1 = word1.len();
let mut l2 = word2.len();
// 有一個字符串為空串
if l1 == 0 {
return l2 as i32;
}
if l2 == 0 {
return l1 as i32;
}
// 讓內(nèi)層單詞較短，可以讓dp數(shù)組較小
if l1 < l2 {
let wt = word1;
word1 = word2;
word2 = wt;
let lt = l1;
l1 = l2;
l2 = lt;
}
// DP 滾動數(shù)組
let mut dp = (0..=l2).collect::<Vec<_>>();
// 計算所有 DP 值
word1.bytes().enumerate().for_each(|(i1, c1)| {
let mut pre = i1;
dp[0] = pre + 1;
word2.bytes().enumerate().for_each(|(i2, c2)| {
let tmp = dp[i2 + 1];
if c1 == c2 {
dp[i2 + 1] = pre;
} else {
// dp[i2 + 1]：相當(dāng)于向第一個單詞插入一個字母
// dp[i2]：相當(dāng)于向第二個單詞插入一個字母
// pre: 相當(dāng)于修改第一個單詞一個字母
dp[i2 + 1] = dp[i2 + 1].min(dp[i2]).min(pre) + 1;
}
pre = tmp;
});
});
dp[l2] as i32
}
}
go：
func minDistance(word1 string, word2 string) int {
l1 := len(word1)
l2 := len(word2)
// 有一個字符串為空串
if l1 == 0 {
return l2
}
if l2 == 0 {
return l1
}
// 讓內(nèi)層單詞較短，可以讓dp數(shù)組較小
if l1 < l2 {
word1, word2 = word2, word1
l1, l2 = l2, l1
}
// DP 滾動數(shù)組
dp := make([]int, l2+1)
for i := 1; i <= l2; i++ {
dp[i] = i
}
// 計算所有 DP 值
for i1, c1 := range word1 {
pre := i1
dp[0] = pre + 1
for i2, c2 := range word2 {
tmp := dp[i2+1]
if c1 == c2 {
dp[i2+1] = pre
} else {
// dp[i2 + 1]：相當(dāng)于向第一個單詞插入一個字母
// dp[i2]：相當(dāng)于向第二個單詞插入一個字母
// pre: 相當(dāng)于修改第一個單詞一個字母
if dp[i2+1] > dp[i2] {
dp[i2+1] = dp[i2]
}
if dp[i2+1] > pre {
dp[i2+1] = pre
}
dp[i2+1] += 1
}
pre = tmp
}
}
return dp[l2]
}
c++：
class Solution {
public:
int minDistance(string word1, string word2) {
int l1 = word1.length(), l2 = word2.length();
// 有一個字符串為空串
if (l1 == 0) {
return l2;
}
if (l2 == 0) {
return l1;
}
// 讓內(nèi)層單詞較短，可以讓dp數(shù)組較小
if (l1 < l2) {
string wt = word1;
word1 = word2;
word2 = wt;
int lt = l1;
l1 = l2;
l2 = lt;
}
// DP 滾動數(shù)組
int dp[l2 + 1];
for (int i = 1; i <= l2; ++i) {
dp[i] = i;
}
// 計算所有 DP 值
for (int i1 = 0; i1 < l1; ++i1) {
int pre = i1;
dp[0] = pre + 1;
for (int i2 = 0; i2 < l2; ++i2) {
const int tmp = dp[i2 + 1];
if (word1[i1] == word2[i2]) {
dp[i2 + 1] = pre;
} else {
// dp[i2 + 1]：相當(dāng)于向第一個單詞插入一個字母
// dp[i2]：相當(dāng)于向第二個單詞插入一個字母
// pre: 相當(dāng)于修改第一個單詞一個字母
dp[i2 + 1] = min(min(dp[i2 + 1], dp[i2]), pre) + 1;
}
pre = tmp;
}
}
return dp[l2];
}
};
python：
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
l1 = len(word1)
l2 = len(word2)
# 有一個字符串為空串
if l1 == 0:
return l2
if l2 == 0:
return l1
# 讓內(nèi)層單詞較短，可以讓dp數(shù)組較小
if l1 < l2:
word1, word2 = word2, word1
l1, l2 = l2, l1
# DP 數(shù)組
dp = [x for x in range(l2 + 1)]
# 計算所有 DP 值
for i1 in range(l1):
pre = i1
dp[0] = pre + 1
for i2 in range(l2):
tmp = dp[i2 + 1]
if word1[i1] == word2[i2]:
dp[i2 + 1] = pre
else:
# dp[i2 + 1]：相當(dāng)于向第一個單詞插入一個字母
# dp[i2]：相當(dāng)于向第二個單詞插入一個字母
# pre: 相當(dāng)于修改第一個單詞一個字母
dp[i2 + 1] = min(dp[i2 + 1], dp[i2], pre) + 1
pre = tmp
return dp[l2]
java：
class Solution {
public int minDistance(String word1, String word2) {
int l1 = word1.length(), l2 = word2.length();
// 有一個字符串為空串
if (l1 == 0) {
return l2;
}
if (l2 == 0) {
return l1;
}
// 讓內(nèi)層單詞較短，可以讓dp數(shù)組較小
if (l1 < l2) {
String wt = word1;
word1 = word2;
word2 = wt;
int lt = l1;
l1 = l2;
l2 = lt;
}
// DP 滾動數(shù)組
int[] dp = new int[l2 + 1];
for (int i = 1; i <= l2; ++i) {
dp[i] = i;
}
// 計算所有 DP 值
for (int i1 = 0; i1 < l1; ++i1) {
int pre = i1;
dp[0] = pre + 1;
for (int i2 = 0; i2 < l2; ++i2) {
final int tmp = dp[i2 + 1];
if (word1.charAt(i1) == word2.charAt(i2)) {
dp[i2 + 1] = pre;
} else {
// dp[i2 + 1]：相當(dāng)于向第一個單詞插入一個字母
// dp[i2]：相當(dāng)于向第二個單詞插入一個字母
// pre: 相當(dāng)于修改第一個單詞一個字母
dp[i2 + 1] = Math.min(Math.min(dp[i2 + 1], dp[i2]), pre) + 1;
}
pre = tmp;
}
}
return dp[l2];
}
}
非常感謝你閱讀本文~
歡迎【點(diǎn)贊】【收藏】【評論】三連走一波~
放棄不難，但堅持一定很酷~
希望我們大家都能每天進(jìn)步一點(diǎn)點(diǎn)~
本文由 二當(dāng)家的白帽子：https://le-yi.blog.csdn.net/ 博客原創(chuàng)~文章來源地址http://www.zghlxwxcb.cn/news/detail-662050.html
到了這里，關(guān)于算法leetcode｜72. 編輯距離（rust重拳出擊）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
