資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中兩個字串的刪除操作
假設我們有兩個單詞 w1 和 w2，我們需要找到使 w1 和 w2 相同所需的最小步數，在每一步中，我們可以在任一字串中刪除一個字元。所以如果輸入像“sea”和“eat”，那麼輸出將是 2，因為我們需要從 w1 中刪除 's'，這將是“ea”，並從 w2 中刪除“eat”中的“t”。然後它們就相同了。
為了解決這個問題，我們將遵循以下步驟
- n := s1 的大小，m := s2 的大小
- 在字串 s1 和 s2 之前新增一個空格，然後相應地更新 s1 和 s2
- 建立一個大小為 (n + 1) x (m + 1) 的表格
- 對於 i := 1 到 m
- dp[0, i] := dp[0, i - 1] + 1
- 對於 i := 1 到 n
- dp[i, 0] := dp[i – 1, 0] + 1
- 對於 i 範圍從 1 到 n
- 對於 j 範圍從 1 到 m
- 如果 s1[i] = s2[j]
- dp[i, j] := dp[i – 1, j - 1]
- 否則 dp[i, j] = dp[i – 1, j] + 1 和 dp[i, j - 1] + 1 的最小值
- 如果 s1[i] = s2[j]
- 對於 j 範圍從 1 到 m
- 返回 dp[n, m]
示例（C++）
讓我們看看以下實現，以便更好地理解 -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minDistance(string s1, string s2) {
int n = s1.size();
int m = s2.size();
s1 = " " + s1;
s2 = " " + s2;
vector < vector <int> > dp(n + 1, vector <int>(m + 1));
for(int i = 1; i <= m; i++){
dp[0][i] = dp[0][i - 1] + 1;
}
for(int i = 1; i <= n; i++){
dp[i][0] = dp[i - 1][0] + 1;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(s1[i] == s2[j]){
dp[i][j] = dp[i - 1][j - 1];
}
else{
dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
}
}
}
return dp[n][m];
}
};
main(){
Solution ob;
vector<int> v = {1,1,1};
cout << (ob.minDistance("sea", "eat"));
}輸入
"sea" "eat"
輸出
2
更新於: 2020-04-29
239 次檢視
廣告