← all categories

Edit Distance 370fe1ee

Levenshtein edit distance (insert/delete/substitute, unit cost) via top-down memoization. For |edit distance| <= k specifically, edit-distance-bounded.h is faster (O(nk) instead of O(nm)).

Time: O(nm). tested

content/dp/edit-distance.h

int editDistanceRec(string &s, string &t, int n, int m, vector<vector<int>> &dp) {
    if (n == 0) return m;
    if (m == 0) return n;
    if (dp[n][m] != -1) return dp[n][m];
    if (s[n - 1] == t[m - 1]) return dp[n][m] = editDistanceRec(s, t, n - 1, m - 1, dp);
    return dp[n][m] = 1 + min({
        editDistanceRec(s, t, n - 1, m, dp),
        editDistanceRec(s, t, n, m - 1, dp),
        editDistanceRec(s, t, n - 1, m - 1, dp)
    });
}

int editDistance(string &s, string &t) {
    int n = (int)s.size(), m = (int)t.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, -1));
    return editDistanceRec(s, t, n, m, dp);
}