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.
Define f(i,j) = minimum operations to convert word1[i:] to word2[j:] (or equivalently prefixes ending at i and j depending on implementation).
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.
If word1[i] == word2[j], then f(i,j) = f(i+1,j+1).
/**
* 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.
*/classSolution {
publicintminDistance(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);
}
privateintdfs(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));
}
}
⏰ 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)#
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.
Express the problem as f(i, j) = minimum operations to convert word1[i:] to word2[j:].
Base cases: if i reached the end of word1 return len(word2) - j; if j reached the end of word2 return len(word1) - i.
Use a 2D cache sized m x n (where m = len(word1), n = len(word2)) initialized to -1 to mark uncomputed states.
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.
This reduces time complexity to O(m*n) and uses O(m*n) extra space for the cache (plus recursion stack).
#include<string>#include<vector>#include<algorithm>classSolution {
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));
returndfs(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));
}
};
classSolution:
defminDistance(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)]
defdfs(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)
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.
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).
classSolution {
publicintminDistance(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 =newint[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];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
classSolution:
defminDistance(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]
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.
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)).
Initialize a 1D array dp of size n+1 with dp[j] = j (base case for converting empty prefix).
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] */).
After processing all rows, dp[n] holds the answer.
classSolution:
defminDistance(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 stringif 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]