Form3_DP/Levenshtein_Distance_Diff_Utility_String.cpp at main · rahulpaul-07/Form3_DP · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>
using namespace std;

string x, y;
int n, m;

int dp[5050][5050];
int backtrack[5050][5050];

int rec(int l1, int l2) {

    // base
    if (l1 == n && l2 == m) return 0;

    // memo
    if (dp[l1][l2] != -1) return dp[l1][l2];

    int ans = 1e9;

    // delete from x
    if (l1 < n) {
        if (rec(l1 + 1, l2) + 1 < ans) {
            ans = rec(l1 + 1, l2) + 1;
            backtrack[l1][l2] = 0;
        }
    }

    // insert from y
    if (l2 < m) {
        if (rec(l1, l2 + 1) + 1 < ans) {
            ans = rec(l1, l2 + 1) + 1;
            backtrack[l1][l2] = 1;
        }
    }

    // replace / match
    if (l1 < n && l2 < m && x[l1] == y[l2]) {
        if (rec(l1 + 1, l2 + 1) + 1 < ans) {
            ans = rec(l1 + 1, l2 + 1) + 1;
            backtrack[l1][l2] = 2;
        }
    }

    return dp[l1][l2] = ans;
}

void generate(int l1, int l2) {

    if (l1 == n && l2 == m) return;

    int ch = backtrack[l1][l2];

    if (ch == 0) {
        cout << "-" << x[l1] << " ";
        generate(l1 + 1, l2);
    }
    else if (ch == 1) {
        cout << "+" << y[l2] << " ";
        generate(l1, l2 + 1);
    }
    else {
        cout << x[l1] << " ";
        generate(l1 + 1, l2 + 1);
    }
}

void solve() {

    cin >> x >> y;

    n = x.length();
    m = y.length();

    memset(dp, -1, sizeof(dp));

    cout << rec(0, 0) << endl;
    generate(0, 0);
    cout << endl;
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    while (t--) solve();
}