Edit Distance

Problem

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word: j j

• Insert a character
• Delete a character
• Replace or substitute a character

Examples

Example 1:

Input:
word1 = "horse", word2 = "ros"
Output:
 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

Input:
word1 = "intention", word2 = "execution"
Output:
 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

Solution

Method 1 - Naive Recursion

Intuition

Work from the current positions in both strings: if characters match, advance both pointers for free; otherwise consider the three operations (insert, delete, replace) on the first string and take the minimal resulting cost.

Approach

1. Define f(i,j) = minimum operations to convert word1[i:] to word2[j:] (or equivalently prefixes ending at i and j depending on implementation).
2. Base cases: if i reached end of word1, need to insert remaining len(word2)-j chars; if j reached end of word2, need to delete remaining len(word1)-i chars.
3. If word1[i] == word2[j], then f(i,j) = f(i+1,j+1).
4. Otherwise f(i,j) = 1 + min( f(i, j+1) /* insert */, f(i+1, j) /* delete */, f(i+1, j+1) /* replace */ ).
5. The naive recursion recomputes many overlapping subproblems and therefore runs in exponential time.

Code

C++

#include <string>
class Solution {
public:
    int minDistance(const std::string& word1, const std::string& word2) {
        return dfs(word1, word2, 0, 0);
    }

private:
    int dfs(const std::string& s1, const std::string& s2, int i, int j) {
        if (i == (int)s1.size()) return (int)s2.size() - j;
        if (j == (int)s2.size()) return (int)s1.size() - i;
        if (s1[i] == s2[j]) return dfs(s1, s2, i+1, j+1);
        int insert = dfs(s1, s2, i, j+1);
        int del = dfs(s1, s2, i+1, j);
        int replace = dfs(s1, s2, i+1, j+1);
        int ans = 1 + std::min(insert, std::min(del, replace));
        return ans;
    }
};

Go

package main

func minDistance(word1 string, word2 string) int {
    return dfs(word1, word2, 0, 0)
}

func dfs(s1, s2 string, i, j int) int {
    if i == len(s1) { return len(s2) - j }
    if j == len(s2) { return len(s1) - i }
    if s1[i] == s2[j] { return dfs(s1, s2, i+1, j+1) }
    insert := dfs(s1, s2, i, j+1)
    del := dfs(s1, s2, i+1, j)
    replace := dfs(s1, s2, i+1, j+1)
    ans := 1
    if insert < del && insert < replace { ans += insert } else if del < replace { ans += del } else { ans += replace }
    return ans
}

Java

/**
 * For each position, check three subproblems:
 * 1. insert
 * 2. delete
 * 3. replace
 * We only modify the first string since no matter which one we choose, the result is the same. 
 * Need to optimize it using cache, which is the idea of dynamic programming. 
 * The key point is to find out the subproblem we have solved duplicately and cache the recursion.
 * Notice that each subproblem is specified by i and j pointers, so we can cache the result of these subproblems. 
 */
class Solution {
    public int minDistance(String word1, String word2) {
        if (word1 == null || word1.length() == 0) return word2.length();
        if (word2 == null || word2.length() == 0) return word1.length();
        
        return dfs(word1, word2, 0, 0);
    }

    private int dfs(String s1, String s2, int i, int j) {
        if (i == s1.length()) {
            return s2.length() - j;
        }
        if (j == s2.length()) {
            return s1.length() - i;
        }
        if (s1.charAt(i) == s2.charAt(j)) return dfs(s1, s2, i+1, j+1);
        int insert = dfs(s1, s2, i, j+1);
        int delete = dfs(s1, s2, i+1, j);
        int replace = dfs(s1, s2, i+1, j+1);
        return 1 + Math.min(insert, Math.min(delete, replace));
    }
}

Python

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        def dfs(i: int, j: int) -> int:
            if i == len(word1):
                return len(word2) - j
            if j == len(word2):
                return len(word1) - i
            if word1[i] == word2[j]:
                return dfs(i+1, j+1)
            insert = dfs(i, j+1)
            delete = dfs(i+1, j)
            replace = dfs(i+1, j+1)
            return 1 + min(insert, delete, replace)

        return dfs(0, 0)

Complexity

• ⏰ Time complexity: O(3^max(m, n)) where m and n are the lengths of word1 and word2 — each mismatch can branch into three recursive calls, giving exponential blowup.
• 🧺 Space complexity: O(max(m, n)) for recursion call stack depth.

Recursion tree (Example 1: word1 = horse, word2 = ros)

graph TD
  A["dfs(0,0)<br/>horse,ros"] --> B["Insert<br/>dfs(0,1)<br/>horse,os"]
  A --> C["Delete<br/>dfs(1,0)<br/>orse,ros"]
  A --> D["Replace<br/>dfs(1,1)<br/>orse,os"]

  %% Replace branch (chosen optimal path)
  D --> D1["match: dfs(2,2)<br/>rse,s"]
  D1 --> D1a["Insert<br/>dfs(2,3)<br/>rse, (empty)<br/>return 3"]
  D1 --> D1b["Delete<br/>dfs(3,2)<br/>se,s"]
  D1b --> D1b1["match -> dfs(4,3)<br/>e, (empty)<br/>return 1"]
  D1 --> D1c["Replace<br/>dfs(3,3)<br/>se, (empty)<br/>return 2"]

  %% computed values
  D1a --> V1["dfs(2,2): candidate=3"]
  D1b1 --> V2["dfs(2,2): candidate=1"]
  D1c --> V3["dfs(2,2): candidate=2"]

  V1 --> D1_val["dfs(2,2) = 1 + min(3,1,2) = 2"]
  V2 --> D1_val
  V3 --> D1_val

  D1_val --> D_res["dfs(1,1) = dfs(2,2) = 2"]
  D_res --> Root_res["dfs(0,0) via Replace = 1 + 2 = 3"]
  Root_res --> Answer["Edit distance = 3"]

  style Answer fill:#e6ffed,stroke:#2ecc71

The diagram shows the main branches; the replace branch leads to the optimal sequence (replace 'h'→'r', delete 'r', delete 'e') producing cost 3.

Method 2 - Top Down DP with Memoization

Intuition

Top-down memoization keeps the simple recursive structure of Method 1 but caches results for already-seen subproblems so they are computed once. The recursive subproblem is fully described by the two indices (i, j) into word1 and word2. When characters match we advance both indices for free; when they differ we consider the three operations (insert, delete, replace) and take the minimum. Storing the result for each (i, j) eliminates exponential recomputation.

Approach

1. Express the problem as f(i, j) = minimum operations to convert word1[i:] to word2[j:].
2. Base cases: if i reached the end of word1 return len(word2) - j; if j reached the end of word2 return len(word1) - i.
3. Use a 2D cache sized m x n (where m = len(word1), n = len(word2)) initialized to -1 to mark uncomputed states.
4. On each call: if cache[i][j] != -1 return it; if word1[i] == word2[j] compute f(i+1, j+1); otherwise compute the three options insert = f(i, j+1), delete = f(i+1, j), replace = f(i+1, j+1), take 1 + min(...), store it in cache[i][j], and return.
5. This reduces time complexity to O(m*n) and uses O(m*n) extra space for the cache (plus recursion stack).

Code

C++

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

class Solution {
public:
    int minDistance(const std::string& word1, const std::string& word2) {
        int m = (int)word1.size();
        int n = (int)word2.size();
        if (m == 0) return n;
        if (n == 0) return m;
        std::vector<std::vector<int>> cache(m, std::vector<int>(n, -1));
        return dfs(word1, word2, 0, 0, cache);
    }

private:
    int dfs(const std::string& s1, const std::string& s2, int i, int j, std::vector<std::vector<int>>& cache) {
        int m = (int)s1.size();
        int n = (int)s2.size();
        if (i == m) return n - j;
        if (j == n) return m - i;
        if (cache[i][j] != -1) return cache[i][j];
        if (s1[i] == s2[j]) return cache[i][j] = dfs(s1, s2, i + 1, j + 1, cache);
        int insert = dfs(s1, s2, i, j + 1, cache);
        int del = dfs(s1, s2, i + 1, j, cache);
        int replace = dfs(s1, s2, i + 1, j + 1, cache);
        return cache[i][j] = 1 + std::min(insert, std::min(del, replace));
    }
};

Go

package main

func minDistance(word1 string, word2 string) int {
    m, n := len(word1), len(word2)
    if m == 0 {
        return n
    }
    if n == 0 {
        return m
    }
    cache := make([][]int, m)
    for i := 0; i < m; i++ {
        cache[i] = make([]int, n)
        for j := 0; j < n; j++ {
            cache[i][j] = -1
        }
    }
    return dfs(word1, word2, 0, 0, cache)
}

func dfs(s1, s2 string, i, j int, cache [][]int) int {
    m, n := len(s1), len(s2)
    if i == m {
        return n - j
    }
    if j == n {
        return m - i
    }
    if cache[i][j] != -1 {
        return cache[i][j]
    }
    if s1[i] == s2[j] {
        cache[i][j] = dfs(s1, s2, i+1, j+1, cache)
        return cache[i][j]
    }
    insert := dfs(s1, s2, i, j+1, cache)
    del := dfs(s1, s2, i+1, j, cache)
    replace := dfs(s1, s2, i+1, j+1, cache)
    cache[i][j] = 1 + min3(insert, del, replace)
    return cache[i][j]
}

func min3(a, b, c int) int {
    if a < b {
        if a < c {
            return a
        }
        return c
    }
    if b < c {
        return b
    }
    return c
}

Java

class Solution {
    public int minDistance(String word1, String word2) {
        if (word1 == null || word2 == null) return -1;
        if (word1.length() == 0) return word2.length();
        if (word2.length() == 0) return word1.length();

        char[] c1 = word1.toCharArray();
        char[] c2 = word2.toCharArray();

        int[][] cache = new int[c1.length][c2.length];
        for (int i = 0; i < c1.length; i++) {
            for (int j = 0; j < c2.length; j++) {
                cache[i][j] = -1;
            }
        }

        return dfs(c1, c2, 0, 0, cache);
    }

    private int dfs(char[] c1, char[] c2, int i, int j, int[][] cache) {
        if (c1.length == i) return c2.length - j;
        if (c2.length == j) return c1.length - i;

        if (cache[i][j] != -1) {
            return cache[i][j];
        }

        if (c1[i] == c2[j]) {
            cache[i][j] = dfs(c1, c2, i + 1, j + 1, cache);
        } else {
            //Case1: insert
            int insert = dfs(c1, c2, i, j + 1, cache);
            //Case2: delete
            int delete = dfs(c1, c2, i + 1, j, cache);
            //Case3: replace
            int replace = dfs(c1, c2, i + 1, j + 1, cache);

            cache[i][j] = Math.min(Math.min(insert, delete), replace) + 1;
        }

        return cache[i][j];
    }
}

Python

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        if m == 0:
            return n
        if n == 0:
            return m
        cache = [[-1] * n for _ in range(m)]

        def dfs(i: int, j: int) -> int:
            if i == m:
                return n - j
            if j == n:
                return m - i
            if cache[i][j] != -1:
                return cache[i][j]
            if word1[i] == word2[j]:
                cache[i][j] = dfs(i+1, j+1)
                return cache[i][j]
            insert = dfs(i, j+1)
            delete = dfs(i+1, j)
            replace = dfs(i+1, j+1)
            cache[i][j] = 1 + min(insert, delete, replace)
            return cache[i][j]

        return dfs(0, 0)

Complexity

• ⏰ Time complexity: O(m*n)
• 🧺 Space complexity: O(m*n)

Method 3 - Bottom up DP

Intuition

Build a table of answers for all prefix pairs. Let dp[i][j] be the minimum number of operations required to convert the first i characters of word1 (i.e. word1[0..i-1]) into the first j characters of word2 (word2[0..j-1]). Smaller prefixes are computed first, so when we compute dp[i][j] the three subproblems we depend on are already available. The first row/column represent conversions to/from the empty string and serve as base cases.

Approach

1. Let m = len(word1) and n = len(word2). Allocate a 2D array dp of size (m+1) x (n+1).
2. Initialize base cases: dp[i][0] = i (delete i chars from word1) and dp[0][j] = j (insert j chars into word1 to make word2).
3. For i from 1 to m and j from 1 to n:
   • If word1[i-1] == word2[j-1] then dp[i][j] = dp[i-1][j-1] (no operation needed).
   • Otherwise dp[i][j] = 1 + min(dp[i-1][j] /* delete */, dp[i][j-1] /* insert */, dp[i-1][j-1] /* replace */).
4. Return dp[m][n] which holds the answer for the full strings.

Optimization: you can reduce space to O(n) by keeping only the current and previous rows (or by using a single row updated carefully), while time remains O(m*n).

Code

C++

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

class Solution {
public:
    int minDistance(const std::string& word1, const std::string& word2) {
        int m = (int)word1.size();
        int n = (int)word2.size();
        if (m == 0) return n;
        if (n == 0) return m;
        std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
        for (int i = 0; i <= m; ++i) dp[i][0] = i;
        for (int j = 0; j <= n; ++j) dp[0][j] = j;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1];
                else dp[i][j] = 1 + std::min(dp[i-1][j], std::min(dp[i][j-1], dp[i-1][j-1]));
            }
        }
        return dp[m][n];
    }
};

Go

package main

func minDistance(word1 string, word2 string) int {
    m, n := len(word1), len(word2)
    if m == 0 {
        return n
    }
    if n == 0 {
        return m
    }
    dp := make([][]int, m+1)
    for i := 0; i <= m; i++ {
        dp[i] = make([]int, n+1)
    }
    for i := 0; i <= m; i++ { dp[i][0] = i }
    for j := 0; j <= n; j++ { dp[0][j] = j }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if word1[i-1] == word2[j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                a := dp[i-1][j]
                b := dp[i][j-1]
                c := dp[i-1][j-1]
                if a < b {
                    if a < c { dp[i][j] = 1 + a } else { dp[i][j] = 1 + c }
                } else {
                    if b < c { dp[i][j] = 1 + b } else { dp[i][j] = 1 + c }
                }
            }
        }
    }
    return dp[m][n]
}

Java

class Solution {
	public int minDistance(String word1, String word2) {
		if (word1 == null || word2 == null) return -1;
		if (word1.length() == 0) return word2.length();
		if (word2.length() == 0) return word1.length();
		
		char[] c1 = word1.toCharArray();
		char[] c2 = word2.toCharArray();
		
		int[][] matched = new int[c1.length + 1][c2.length + 1];
		//matched[length of c1 already been matched][length of c2 already been matched]
		
		for (int i = 0; i <= c1.length; i++) {
			matched[i][0] = i;
		}
		for (int j = 0; j <= c2.length; j++) {
			matched[0][j] = j;
		}
		
		for (int i = 0; i < c1.length; i++) {
			for (int j = 0; j < c2.length; j++) {
				if (c1[i] == c2[j]) {
					matched[i + 1][j + 1] = matched[i][j];
				} else {
					matched[i + 1][j + 1] = Math.min(Math.min(matched[i][j + 1], matched[i + 1][j]), matched[i][j]) + 1;
					//Since it is bottom up, we are considering in the ascending order of indexes.
					//Insert means plus 1 to j, delete means plus 1 to i, replace means plus 1 to both i and j. 
					//above sequence is delete, insert and replace. 
				}
			}
		}
		
		return matched[c1.length][c2.length];
	}
}

Python

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        if m == 0:
            return n
        if n == 0:
            return m
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m + 1):
            dp[i][0] = i
        for j in range(n + 1):
            dp[0][j] = j
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
        return dp[m][n]

Complexity

• ⏰ Time complexity: O(m*n) — we fill an (m+1) x (n+1) table once.
• 🧺 Space complexity: O(m*n) — the DP table; can be reduced to O(min(m,n)) with the optimized method.

Method 4 - Space Optimized DP

Intuition

The bottom-up recurrence for edit distance uses only the previous row and the current row when filling the DP table: dp[i][j] depends on dp[i-1][j], dp[i][j-1] and dp[i-1][j-1]. Therefore we can avoid storing the full 2D table and keep only a single 1D array (or two rows) of length min(m,n)+1. Choosing the shorter string as the inner dimension minimizes memory usage.

Approach

1. Let m = len(word1), n = len(word2). If m < n, swap the strings so that the second string is the shorter one (this ensures the 1D array has size n+1 where n = min(original lengths)).
2. Initialize a 1D array dp of size n+1 with dp[j] = j (base case for converting empty prefix).
3. Iterate i from 1..m, maintaining a prevDiagonal value representing dp[i-1][j-1] from the previous iteration. Update dp[j] in-place using the recurrence:
   • if word1[i-1] == word2[j-1] then dp[j] = prevDiagonal;
   • else dp[j] = 1 + min(dp[j] /* old dp[i-1][j] */, dp[j-1] /* dp[i][j-1] after update */, prevDiagonal /* dp[i-1][j-1] */).
4. After processing all rows, dp[n] holds the answer.

Code

Java

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        if (m == 0) return n;
        if (n == 0) return m;
        // Ensure word2 is the shorter string to minimize space
        if (m < n) {
            String tmp = word1; word1 = word2; word2 = tmp;
            int t = m; m = n; n = t;
        }

        int[] dp = new int[n + 1];
        for (int j = 0; j <= n; j++) dp[j] = j;

        for (int i = 1; i <= m; i++) {
            int prevDiagonal = dp[0]; // dp[i-1][0]
            dp[0] = i; // dp[i][0]
            for (int j = 1; j <= n; j++) {
                int temp = dp[j]; // will become prevDiagonal for next j
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[j] = prevDiagonal;
                } else {
                    dp[j] = 1 + Math.min(dp[j] /* old dp[i-1][j] */, Math.min(dp[j - 1] /* dp[i][j-1] */, prevDiagonal /* dp[i-1][j-1] */));
                }
                prevDiagonal = temp;
            }
        }
        return dp[n];
    }
}

C++

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

class Solution {
public:
    int minDistance(const std::string& a, const std::string& b) {
        std::string s1 = a, s2 = b;
        int m = (int)s1.size(), n = (int)s2.size();
        if (m == 0) return n;
        if (n == 0) return m;
        if (m < n) { std::swap(s1, s2); std::swap(m, n); }
        std::vector<int> dp(n + 1);
        for (int j = 0; j <= n; ++j) dp[j] = j;
        for (int i = 1; i <= m; ++i) {
            int prevDiagonal = dp[0];
            dp[0] = i;
            for (int j = 1; j <= n; ++j) {
                int temp = dp[j];
                if (s1[i - 1] == s2[j - 1]) dp[j] = prevDiagonal;
                else dp[j] = 1 + std::min(dp[j], std::min(dp[j - 1], prevDiagonal));
                prevDiagonal = temp;
            }
        }
        return dp[n];
    }
};

Go

package main

func minDistance(word1 string, word2 string) int {
    m, n := len(word1), len(word2)
    if m == 0 { return n }
    if n == 0 { return m }
    // ensure word2 is the shorter string
    if m < n { word1, word2 = word2, word1; m, n = n, m }

    dp := make([]int, n+1)
    for j := 0; j <= n; j++ { dp[j] = j }

    for i := 1; i <= m; i++ {
        prevDiagonal := dp[0]
        dp[0] = i
        for j := 1; j <= n; j++ {
            temp := dp[j]
            if word1[i-1] == word2[j-1] {
                dp[j] = prevDiagonal
            } else {
                a := dp[j]     // old dp[i-1][j]
                b := dp[j-1]   // dp[i][j-1]
                c := prevDiagonal // dp[i-1][j-1]
                // compute 1 + min(a,b,c)
                minab := a
                if b < minab { minab = b }
                if c < minab { minab = c }
                dp[j] = 1 + minab
            }
            prevDiagonal = temp
        }
    }
    return dp[n]
}

Python

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        if m == 0:
            return n
        if n == 0:
            return m
        # ensure word2 is the shorter string
        if m < n:
            word1, word2 = word2, word1
            m, n = n, m

        dp = list(range(n + 1))
        for i in range(1, m + 1):
            prevDiagonal = dp[0]
            dp[0] = i
            for j in range(1, n + 1):
                temp = dp[j]
                if word1[i-1] == word2[j-1]:
                    dp[j] = prevDiagonal
                else:
                    dp[j] = 1 + min(dp[j], dp[j-1], prevDiagonal)
                prevDiagonal = temp
        return dp[n]

Complexity

• ⏰ Time complexity: O(m*n) — still need to process each cell of the DP table row-by-row.
• 🧺 Space complexity: O(min(m,n)) — using a single 1D array of length min(m,n)+1.