Example: Minimum Edit Distance - rFronteddu/general_wiki GitHub Wiki

Assume to have two strings, what is the minimum number of edits {add, replace, delete} to get from s1 to s2?

// S1 = azced
// S2 = abcdef
//     a b c d e f
//   0 1 2 3 4 5 6
// a 1 0 1 2 3 4 5
// z 2 1 1 2 3 4 5
// c 3 2 2 1 2 3 4
// e 4 3 3 2 2 2 3
// d 5 4 4 3 2 3 3
// First row/col is how many changes to get from empty string to S1/S2
// S1[1..n]
// S2[1..m]
MED(X, Y)
    let d[0..S1.len, 0..S2.len] be a table
    for i = 1 to S1.len
        d[i, 0] = i
    for j = 1 to S2.len
        d[0,j] = j

    for i = 1 to S1.len
         for j = 1 to S2.len
             if S1[i]==S2[j]
                 // same, no changes needed
                 d[i,j] = d[i-1, j-1]
             else 
                 d[i,j] = 1 + min (d[i-1,j-1], d[i-1, j], d[i,j-1])
                //                   edit        del        add        
    print("Number of operations: " + d[S1.len, S2.len])

    i = S1.len
    j = S2.len

    l = []
    while i > 0 && j > 0
        if(S1[i] == S2[j])
            l.push("same")
            i--
            j--
        else if d[i,j] == 1 + d[i-1,j-1]
            l.push("edit")
            i--
            j--
        else if d[i,j] == 1 + d[i-1,j]
            l.push("del")
            i--
        else
            l.push("add")
            j--
    print("Operations:")
    for el : l 
        print(el)