Final: Edit Distance

Lab C++ Advanced 30 points

Print the fewest single-letter edits (insert, delete or replace) that turn the first word into the second.

Input

Two words (at most 1000 letters each).

Output

One number.

Example

Input

horse
ros

Output

Sample input available Sample output available

Editor

C++

Hints

dp[i][0] = i, dp[0][j] = j.

Different letters: 1 + min(delete, insert, replace).

Solution explanation

The same table idea as LCS: O(n × m).

Show solution

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1));
    for (int i = 0; i <= n; i++) dp[i][0] = i;
    for (int j = 0; j <= m; j++) dp[0][j] = j;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dp[i][j] = (a[i - 1] == b[j - 1]) ? dp[i - 1][j - 1]
                                               : 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
    cout << dp[n][m] << endl;
    return 0;
}

Output

Answer