資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++實現兩個字串的最小ASCII刪除和
假設我們有兩個單詞 w1 和 w2，我們需要找到使 w1 和 w2 相同的最小ASCII刪除字元和，在每一步中，我們可以在任一字串中刪除一個字元。例如，輸入是“sea”和“eat”，那麼輸出將是231，因為我們需要從 w1 中刪除 's'，得到 “ea”，並從 w2 中刪除 't'，得到 “ea”。然後它們相同。從“eat”中刪除't' 會將116新增到總和中，最終兩個字串相同，115 + 116 = 231 是實現此目標的最小可能總和。
為了解決這個問題，我們將遵循以下步驟：
- n := s1 的大小，m := s2 的大小
- 在字串 s1 和 s2 之前新增一個空格，然後相應地更新 s1 和 s2。
- 建立一個大小為 (n + 1) x (m + 1) 的表格。
- 對於 i := 1 到 m
- dp[0, i] := dp[0, i - 1] + s2[i]
- 對於 i := 1 到 n
- dp[i, 0] := dp[i – 1, 0] + s1[i]
- 對於 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 minimumDeleteSum(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] + s2[i];
}
for(int i = 1; i <= n; i++){
dp[i][0] = dp[i - 1][0] + s1[i];
}
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] + s1[i], dp[i][j - 1] + s2[j]);
}
}
}
return dp[n][m];
}
};
main(){
Solution ob;
cout << (ob.minimumDeleteSum("sea", "eat"));
}輸入
"sea" "eat"
輸出
231
更新於：2020年4月29日
393 次瀏覽
廣告