Edit distance

The fewest single-character inserts, deletes and replacements needed to turn one string into another.

Time O(m × n)Space O(m × n)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

dp[i, j] is the cost of turning the first i characters of a into the first j of b. Matching characters cost nothing. Otherwise pay 1 and take the cheapest of replace (diagonal), delete (up) or insert (left).

Code

C++PythonC#

int editDistance(const string& a, const string& b) {
    int n = (int)a.size(), m = (int)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 - 1],
                           dp[i - 1][j], dp[i][j - 1]});
    return dp[n][m];
}

def edit_distance(a: str, b: str) -> int:
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(len(a) + 1): dp[i][0] = i
    for j in range(len(b) + 1): dp[0][j] = j
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])
    return dp[len(a)][len(b)]

public static int EditDistance(string a, string b) {
    var dp = new int[a.Length + 1, b.Length + 1];
    for (int i = 0; i <= a.Length; i++) dp[i, 0] = i;
    for (int j = 0; j <= b.Length; j++) dp[0, j] = j;
    for (int i = 1; i <= a.Length; i++)
        for (int j = 1; j <= b.Length; j++)
            dp[i, j] = a[i - 1] == b[j - 1]
                ? dp[i - 1, j - 1]
                : 1 + Math.Min(dp[i - 1, j - 1],
                      Math.Min(dp[i - 1, j], dp[i, j - 1]));
    return dp[a.Length, b.Length];
}

Tips

The first column is "delete everything", the first row is "insert everything".
Also called Levenshtein distance. Spell checkers and fuzzy search are built on it.

In the .NET library

There is no Levenshtein method in the base class library, so this is one you write yourself or take from a NuGet package.