Formula: the Wagner-Fischer dynamic program, \(D[0,0]=0\), \(D[i,0] = i c_{del}\), \(D[0,j] = j c_{ins}\), \(D[i,j] = \min(D[i-1,j]+c_{del},\, D[i,j-1]+c_{ins},\, D[i-1,j-1] + c_{sub}[s_1[i] \ne s_2[j]])\), answer at \(D[m,n]\). Only the previous row is kept, so memory is O(n); the recurrence is unchanged. Inputs are compared element by element, so token vectors work as well as strings. Unit costs give Levenshtein's metric; unequal costs break symmetry, deliberately.
References
Levenshtein (1966), Soviet Physics Doklady 10:707-710 (the metric); Wagner and Fischer (1974), JACM 21:168-173 (the dynamic program). Neither was fetchable – Doklady is not online and JACM is paywalled – so this is the standard published recurrence, anchored in the harness against R's own utils::adist.
Examples
V <- c(1, 2, 3, 4, 5, 6, 7, 8)
Editdist(V, V)
#> [1] 0