Edit Distance DP

Concept

Edit distance (Levenshtein distance) is the minimum number of operations (insert, delete, replace) to transform one string into another. Use 2D memoization where mem[i][j] = edit distance between the first i characters of word1 and first j characters of word2.

When to Use

  • ▸Measuring similarity between two strings
  • ▸Spell checking and autocorrect
  • ▸DNA sequence alignment
  • ▸Any problem asking minimum operations to transform string A to string B

Intuition

Compare characters from the end. If they match, no operation needed — move both pointers back. If they don't match, try all three operations: insert (move j back), delete (move i back), replace (move both back). Each costs 1 operation. Take the minimum. The 2D table builds up from empty strings: transforming empty to a string of length j costs j insertions.

Complexity

Time
O(n * m)
Space
O(n * m)

Template Code

cpp
#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> mem;

int f(int i, int j, string &word1, string &word2){
    if(i == 0) return j;
    if(j == 0) return i;

    if(mem[i][j] != -1) return mem[i][j];

    if(word1[i-1] == word2[j-1]) return mem[i][j] = f(i-1, j-1, word1, word2);

    int ins = f(i, j-1, word1, word2);
    int del = f(i-1, j, word1, word2);
    int rep = f(i-1, j-1, word1, word2);

    return mem[i][j] = 1 + min({ins, del, rep});
}

int minDistance(string word1, string word2) {
    int n = word1.size(), m = word2.size();
    mem.assign(n+1, vector<int>(m+1, -1));
    return f(n, m, word1, word2);
}

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    string word1, word2;
    cin >> word1 >> word2;

    cout << minDistance(word1, word2) << "\n";

    return 0;
}

// Sample Input:
// horse ros
//
// Sample Output:
// 3