Edit Distance Algorithm

1. Algorithm Explanation

The Edit Distance (or Levenshtein distance) between two strings s of length n and t of length m is the minimum number of single-character insertions, deletions, or substitutions required to transform s into t.

We define a DP table dp[i][j] = edit distance between s[0..i-1] and t[0..j-1]. The recurrence is:

• dp[0][0] = 0 (empty → empty costs 0)
• dp[i][0] = i (delete all i characters)
• dp[0][j] = j (insert all j characters)
• For i>0, j>0:

  dp[i][j] = min(
      dp[i-1][j]   + 1,    // deletion
      dp[i][j-1]   + 1,    // insertion
      dp[i-1][j-1] + cost  // substitution (cost = 0 if s[i-1]==t[j-1], else 1)
  )

Time Complexity

Filling an (n+1)×(m+1) table takes O(n·m) time.

Memory Complexity

Naïvely, we store the full table in O(n·m) space. It can be reduced to O(min(n,m)) by keeping only two rows at once.

2. Easy Problems

2.1 Problem: LeetCode 72 – Edit Distance

Compute the minimum edit distance between two given strings.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

int minDistance(const std::string &s, const std::string &t) {
    int n = s.size(), m = t.size();
    std::vector<std::vector<int>> dp(n+1, std::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) {
            int cost = (s[i-1] == t[j-1] ? 0 : 1);
            dp[i][j] = std::min({
                dp[i-1][j] + 1,
                dp[i][j-1] + 1,
                dp[i-1][j-1] + cost
            });
        }
    }
    return dp[n][m];
}

int main() {
    std::cout << minDistance("kitten", "sitting") << "\n";  // Outputs 3
    return 0;
}

2.2 Problem: LeetCode 161 – One Edit Distance

Check if two strings are exactly one edit apart.

#include <iostream>
#include <string>
#include <cmath>

bool isOneEditDistance(const std::string &s, const std::string &t) {
    int n = s.size(), m = t.size();
    if (std::abs(n - m) > 1) return false;
    int i = 0, j = 0, edits = 0;
    while (i < n && j < m) {
        if (s[i] == t[j]) {
            ++i; ++j;
        } else {
            if (++edits > 1) return false;
            if (n > m) ++i;
            else if (n < m) ++j;
            else { ++i; ++j; }
        }
    }
    edits += (i < n) + (j < m);
    return edits == 1;
}

int main() {
    std::cout << std::boolalpha
              << isOneEditDistance("abc", "ab") << "\n";  // true
    return 0;
}

3. Intermediate Problems

3.1 Problem: LeetCode 583 – Delete Operation for Two Strings

Return the minimum number of delete operations on the two strings to make them equal. This equals n + m – 2·LCS(s, t), but can be solved by edit‐distance DP restricted to deletions only.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

int minDistanceDelete(const std::string &s, const std::string &t) {
    int n = s.size(), m = t.size();
    std::vector<std::vector<int>> dp(n+1, std::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) {
            if (s[i-1] == t[j-1])
                dp[i][j] = dp[i-1][j-1];
            else
                dp[i][j] = 1 + std::min(dp[i-1][j], dp[i][j-1]);
        }
    }
    return dp[n][m];
}

int main() {
    std::cout << minDistanceDelete("sea", "eat") << "\n";  // Outputs 2
    return 0;
}

3.2 Problem: LeetCode 1312 – Minimum Insertion Steps to Make a String Palindrome

Find the minimum number of insertions to make s a palindrome. Equivalent to n – LPS(s), but solvable by DP on edit distance where only insertions are allowed.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

int minInsertionsPalindrome(const std::string &s) {
    int n = s.size();
    std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));
    for (int len = 2; len <= n; ++len) {
        for (int i = 0; i + len - 1 < n; ++i) {
            int j = i + len - 1;
            if (s[i] == s[j])
                dp[i][j] = dp[i+1][j-1];
            else
                dp[i][j] = 1 + std::min(dp[i+1][j], dp[i][j-1]);
        }
    }
    return dp[0][n-1];
}

int main() {
    std::cout << minInsertionsPalindrome("leetcode") << "\n";  // Outputs 5
    return 0;
}

4. Hard Problem

4.1 Problem: Damerau–Levenshtein Distance (with transpositions)

Compute the edit distance allowing transposition of two adjacent characters as one operation. This generalizes Levenshtein by adding one more case.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <limits>

int damerauLevenshtein(const std::string &s, const std::string &t) {
    int n = s.size(), m = t.size();
    const int INF = n + m;
    std::vector<std::vector<int>> dp(n+2, std::vector<int>(m+2, INF));
    dp[0][0] = INF;
    for (int i = 0; i <= n; ++i) {
        dp[i+1][1] = i;
        dp[i+1][0] = INF;
    }
    for (int j = 0; j <= m; ++j) {
        dp[1][j+1] = j;
        dp[0][j+1] = INF;
    }
    std::vector<int> last(256, 0);
    for (int i = 1; i <= n; ++i) {
        int lastMatchCol = 0;
        for (int j = 1; j <= m; ++j) {
            int i1 = last[t[j-1]];
            int j1 = lastMatchCol;
            int cost = (s[i-1] == t[j-1]) ? 0 : 1;
            if (cost == 0) lastMatchCol = j;
            dp[i+1][j+1] = std::min({
                dp[i][j] + cost,                   // substitution
                dp[i+1][j] + 1,                    // insertion
                dp[i][j+1] + 1,                    // deletion
                dp[i1][j1] + (i - i1 - 1) + 1 + (j - j1 - 1)  // transposition
            });
        }
        last[s[i-1]] = i;
    }
    return dp[n+1][m+1];
}

int main() {
    std::cout << damerauLevenshtein("CA", "ABC") << "\n";  // Outputs 2
    return 0;
}