Edit distance ---- Minimum number of edits needed to transform the first string into the second string

Levenshtein distance:
either insert, delete, or substitute.

Suppose the length of A and B are a and b. and their distance is E(A,B)
There are two cases:
A[a-1]== B[b-1]    -------E(A[0...a-1],B[0...b-1])  = E(A[0...a-2], B[0...b-2])
A[a-1]!= B[b-1]   ------- E(A[0...a-1],B[0...b-1])  = 1 + min ( E(A[0...a-2],B[0...b-2]), E(A[0...a-1],B[0...b-2]), E(A[0...a-2],B[0...b-1])  ), viz., all three cases can happen, but we choose the minimum one.

C++:
iota(D.begin(), D.end(), val)   assign value to D from val and ++val everytime

The easy way is to implement it as a two dimentional maxtrix D. but here it is a ONE dimensional array.
Notice that at each step: we need to update the D[0] to i, and store D[i-1][j-1] (which is previous D[j-1])

Code:

int LevenDistance(string A, string B)
{
    if (A.size() < B.size())  swap(A,B);
    vector D( B.size()+1 );
    iota(D.begin(), D.end(), 0);

    for (int i=1; i<=A.size(); ++i)
    {
        int pre_i_1_j_1 = D[0];
        D[0] = i
        for (int j=1; j<=B.size(); ++j)
        {
            int pre_i_1_j = D[j];
            D[j] = A[i-1] == B[j-1] ? pre_i_1_j_1 : 1 + min( pre_i_1_j_1, min(D[j-1], D[j]) );
            pre_i_1_j_1 = pre_i_1_j;
        }
    }
    return D.back();
}