資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的編輯距離
假設我們有兩個單詞 word1 和 word2，我們需要找到將 word1 轉換為 word2 所需的最少操作次數。操作可以是三種類型：插入一個字元、刪除一個字元和替換一個字元。因此，如果輸入字串為“evaluate”和“fluctuate”，則結果將為 5。
為了解決這個問題，我們將遵循以下步驟：
n := w1 的大小，m := w2 的大小，
建立一個大小為 n + 1 的陣列 dp
對於 i 的範圍從 0 到 n
dp[i] := 一個大小為 m + 1 的新陣列
對於 j 的範圍從 0 到 m −
dp[i, j] := 0
如果 i = 0，則 dp[i,j] = j
否則，當 j = 0 時，則 dp[i, j] := i
w1 := 空格並連線 w1，w2 := 空格並連線 w2
對於 i 的範圍從 1 到 n
對於 j 的範圍從 1 到 m
如果 w1[i] 不等於 w2[j]，則 dp[i, j] := 1 + dp[i – 1, j]、dp[i, j - 1]、dp[i – 1, j – 1] 的最小值
否則 dp[i, j] := dp[i – 1, j – 1]
返回 dp[n, m]
示例
讓我們看看以下實現以更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minDistance(string w1, string w2) {
int n = w1.size();
int m =w2.size();
int** dp = new int*[n+1];
for(int i =0;i<=n;i++){
dp[i] = new int[m+1];
for(int j=0;j<=m;j++){
dp[i][j]=0;
if(i==0)dp[i][j]=j;
else if(j==0)dp[i][j] = i;
}
}
w1 = " " + w1;
w2 = " " + w2;
for(int i =1;i<=n;i++){
for(int j = 1;j<=m;j++){
if(w1[i] !=w2[j]){
dp[i][j] = 1+min({dp[i-1][j],dp[i][j-1],dp[i1][j-1]});
} else {
dp[i][j] = dp[i-1][j-1];
}
}
}
return dp[n][m];
}
};
main(){
Solution ob;
cout << (ob.minDistance("fluctuate", "evaluate"));
}輸入
"fluctuate" "evaluate"
輸出
5
更新於: 2020-05-26
389 次檢視
廣告