2377 . 综合题 Puls

编辑距离【CSP 2023 入门级第一轮】)

给定两个字符串,每次操作可以选择删除(Delete)、插入(Insert)、替换(Replace),一个字符,求将第一个字符串转换为第二个字符串所需要的最少操作次数。

#include <iostream> 
#include <string> 
#include <vector> 
using namespace std;
int min(int x, int y, int z) {
    return min(min(x, y), z);
}
int edit_dist_dp(string str1, string str2) {
    int m = str1.length();
    int n = str2.length();
    vector < vector < int >> dp(m + 1, vector < int > (n + 1));
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0)
                dp[i][j] = ①;
            else if (j == 0)
                dp[i][j] = ②;
            else if (③)
                dp[i][j] = ④;
            else
                dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], ⑤);
        }
    }
    return dp[m][n];
}
int main() {
    string str1, str2;
    cin >> str1 >> str2;
    cout << "Mininum number of operation:" << edit_dist_dp(str1, str2) <<  endl;
    return 0;
}
1 . (单选题)

①处应填( )

2 . (单选题)

②处应填( )

3 . (单选题)

③处应填( )

4 . (单选题)

④处应填( )

5 . (单选题)

⑤处应填( )

凤鸣
简单
0
收藏
题解讨论
反馈