← all categories

Edit Distance Bounded 870c9d9c

"Is edit distance <= k?" in O(nk) instead of O(nm), by restricting the DP to the diagonal band |i - j| <= k (any optimal alignment outside the band would need > k edits already). Returns true iff editDistance(s, t) <= k.

Time: O(nk). tested

content/dp/edit-distance-bounded.h

bool editDistanceWithinK(string &s, string &t, int k) {
    int n = (int)s.size(), m = (int)t.size();
    if (abs(n - m) > k) return false;
    const int BIG = k + 1;

    vector<int> prev(m + 1), curr(m + 1);
    for (int j = 0; j <= m; j++) prev[j] = (j <= k ? j : BIG);

    for (int i = 1; i <= n; i++) {
        int lo = max((ll)1, i - k), hi = min((ll)m, i + k);
        curr[0] = (i <= k ? i : BIG);
        // reset curr[lo-1] BEFORE the loop: j=lo reads curr[j-1], and curr is reused
        // (ping-ponged with prev) across rounds, so it otherwise holds a stale value
        // from 2 rounds ago instead of "out of band" — this was a real bug, caught by
        // stress-testing against editDistance() on a random case.
        if (lo > 1) curr[lo - 1] = BIG;
        for (int j = lo; j <= hi; j++) {
            int cost = (s[i - 1] == t[j - 1] ? 0 : 1);
            int ins = curr[j - 1] + 1, del = prev[j] + 1, sub = prev[j - 1] + cost;
            curr[j] = min({ins, del, sub});
        }
        if (hi < m) curr[hi + 1] = BIG;
        swap(prev, curr);
    }

    return prev[m] <= k;
}