資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式：查詢兩個字串之間的最小編輯距離
假設我們有兩個單詞S和T，我們需要找到將S轉換為T所需的最小運算元。
- 操作可以分為三種類型：
- 插入一個字元；
- 刪除一個字元；
因此，如果輸入字串是“evaluate”和“fluctuate”，則結果為5。
為了解決這個問題，我們將遵循以下步驟：
n := s的長度，m := t的長度；
建立一個大小為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；
s := 在s前面新增一個空格，t := 在t前面新增一個空格；
對於i從1到n：
對於j從1到m：
如果s[i]不等於t[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 s, string t) {
int n = s.size();
int m =t.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;
}
}
s = " " + s;
t = " " + t;
for(int i =1;i<=n;i++){
for(int j = 1;j<=m;j++){
if(s[i] !=t[j]){
dp[i][j] = 1+min({dp[i-1][j],dp[i][j-1],dp[i-1][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年10月7日
410 次瀏覽
廣告