72. Edit Distance
July 28, 2025 · View on GitHub
Given two words word1 and word2, calculate the minimum number of operations required to convert word1 to word2.
You can perform the following operations on a word:
-
Insert a character
-
Delete a character
-
Replace a character
-
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')
Constraints:
- 0 <= word1.length, word2.length <= 500
- word1 and word2 consist of lowercase English letters
Approach
The edit distance problem has finally arrived, and this problem can seem extremely complex without an understanding of dynamic programming.
Edit distance is a classic problem solved using dynamic programming. Though this problem looks complex at first, dynamic programming elegantly computes the minimal edit distance.
Here I'll analyze this problem thoroughly using the five steps of dynamic programming:
1. Define the dp array (dp table) and the meaning of the indices
dp[i][j] indicates the minimum edit distance between the substring of word1 ending at index i-1 and the substring of word2 ending at index j-1.
Some might ask why this indicates the substring ending at i-1 rather than i.
The reason for defining it this way is explained in detail in 0718.Maximum Length of Repeated Subarray.
You could use i! Opting for i-1 simplifies subsequent initialization of the dp array.
2. Determine the recurrence formula
When determining the recurrence formula, first consider all possible editing operations, summarized below:
if (word1[i - 1] == word2[j - 1])
No operation
if (word1[i - 1] != word2[j - 1])
Insert
Delete
Replace
These are the four cases.
if (word1[i - 1] == word2[j - 1]) indicates no editing is needed, so dp[i][j] should equal dp[i - 1][j - 1], i.e., dp[i][j] = dp[i - 1][j - 1];.
Some may not understand right away why dp[i][j] = dp[i - 1][j - 1].
Recall the definition of dp[i][j]. If word1[i - 1] equals word2[j - 1], no editing is needed, and the minimum edit distance between the substring of word1 ending at i-2 and the substring of word2 ending at j-2, which is dp[i - 1][j - 1], is dp[i][j].
If some explanations are unclear, referring back to the definition of dp[i][j] can clarify it.
The key to successfully applying dynamic programming here is a correct understanding of the definition of dp[i][j].
if (word1[i - 1] != word2[j - 1]), editing is necessary. How can you edit it?
-
Operation 1: Deleting a character from
word1makes it align with a substring ofword2up toj-2, requiring an additional operation. Thus,dp[i][j] = dp[i - 1][j] + 1;. -
Operation 2: Deleting a character from
word2aligns it with a substring ofword1up toi-2, also requiring an additional operation, sodp[i][j] = dp[i][j - 1] + 1;.
Some might notice these are deletion operations, what about insertion?
Inserting a character in word2 is equivalent to deleting a character in word1. For instance, word1 = "ad", word2 = "a". Removing 'd' in word1 to transform it into a and adding 'd' to word2 to transform it into ad are essentially requiring the same number of operations! The dp array is illustrated as follows:
a a d
+-----+-----+ +-----+-----+-----+
| 0 | 1 | | 0 | 1 | 2 |
+-----+-----+ ===> +-----+-----+-----+
a | 1 | 0 | a | 1 | 0 | 1 |
+-----+-----+ +-----+-----+-----+
d | 2 | 1 |
+-----+-----+
Operation 3: Substituting a character: replace word1[i - 1] to match word2[j - 1] with no need for insertion or deletion.
You only need one substitution operation to make word1[i - 1] and word2[j - 1] identical. Hence, dp[i][j] = dp[i - 1][j - 1] + 1;.
In summary, when if (word1[i - 1] != word2[j - 1]), take the minimum of these: dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;.
The recursion formula in code:
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
}
else {
dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
}
3. Initialization of the dp array
Revisiting the definition of dp[i][j]:
dp[i][j] indicates the minimum edit distance between the substring ending at i-1 in word1 and j-1 in word2.
What do dp[i][0] and dp[0][j] indicate?
dp[i][0]: indicates the minimum edit distance between the substring of word1 ending at i-1 and an empty string word2.
Thus, dp[i][0] should be i, as you would need to delete all characters in word1, i.e., dp[i][0] = i;.
Similarly, dp[0][j] = j;.
So the C++ code:
for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;
for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;
4. Determine the order of traversal
In these recurrence formulas:
dp[i][j] = dp[i - 1][j - 1]dp[i][j] = dp[i - 1][j - 1] + 1dp[i][j] = dp[i][j - 1] + 1dp[i][j] = dp[i - 1][j] + 1
It is evident that dp[i][j] relies on the values to its left, above, and diagonally above-left, as shown:
Thus, the dp matrix must be traversed from left to right and top to bottom.
The code:
for (int i = 1; i <= word1.size(); i++) {
for (int j = 1; j <= word2.size(); j++) {
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
}
else {
dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
}
}
}
5. Demonstrate and Verify the dp array
Taking example 1, input: word1 = "horse", word2 = "ros", the dp matrix state is:
With this, the dynamic programming analysis is complete. Here's the C++ code:
class Solution {
public:
int minDistance(string word1, string word2) {
vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;
for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;
for (int i = 1; i <= word1.size(); i++) {
for (int j = 1; j <= word2.size(); j++) {
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
}
else {
dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
}
}
}
return dp[word1.size()][word2.size()];
}
};
- Time complexity: O(n * m)
- Space complexity: O(n * m)
Other Language Versions
Java:
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
int[][] dp = new int[m + 1][n + 1];
// Initialize
for (int i = 1; i <= m; i++) {
dp[i][0] = i;
}
for (int j = 1; j <= n; j++) {
dp[0][j] = j;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// Since the valid dp array starts at 1
// The current character positions in the string are i-1 | j-1
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
}
}
}
return dp[m][n];
}
Python:
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
dp = [[0] * (len(word2)+1) for _ in range(len(word1)+1)]
for i in range(len(word1)+1):
dp[i][0] = i
for j in range(len(word2)+1):
dp[0][j] = j
for i in range(1, len(word1)+1):
for j in range(1, len(word2)+1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
return dp[-1][-1]
Go:
func minDistance(word1 string, word2 string) int {
m, n := len(word1), len(word2)
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
for i := 0; i < m+1; i++ {
dp[i][0] = i // transforming word1[i] to word2[0], delete word1[i], needs i operations
}
for j := 0; j < n+1; j++ {
dp[0][j] = j // transforming word1[0] to word2[j], insert word1[j], needs j operations
}
for i := 1; i < m+1; i++ {
for j := 1; j < n+1; j++ {
if word1[i-1] == word2[j-1] {
dp[i][j] = dp[i-1][j-1]
} else { // Min(insert, delete, replace)
dp[i][j] = Min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1
}
}
}
return dp[m][n]
}
func Min(args ...int) int {
min := args[0]
for _, item := range args {
if item < min {
min = item
}
}
return min
}
JavaScript:
const minDistance = (word1, word2) => {
let dp = Array.from(Array(word1.length + 1), () => Array(word2.length+1).fill(0));
for(let i = 1; i <= word1.length; i++) {
dp[i][0] = i;
}
for(let j = 1; j <= word2.length; j++) {
dp[0][j] = j;
}
for(let i = 1; i <= word1.length; i++) {
for(let j = 1; j <= word2.length; j++) {
if(word1[i-1] === word2[j-1]) {
dp[i][j] = dp[i-1][j-1];
} else {
dp[i][j] = Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 1);
}
}
}
return dp[word1.length][word2.length];
};
TypeScript:
function minDistance(word1: string, word2: string): number {
/**
dp[i][j]: minimum number of operations for word1's first i characters turned into word2's first j characters
dp[0][0]=0：indicates the operation number for converting 0 characters (empty string) from word1 and word2
*/
const length1: number = word1.length,
length2: number = word2.length;
const dp: number[][] = new Array(length1 + 1).fill(0)
.map(_ => new Array(length2 + 1).fill(0));
for (let i = 0; i <= length1; i++) {
dp[i][0] = i;
}
for (let i = 0; i <= length2; i++) {
dp[0][i] = i;
}
for (let i = 1; i <= length1; i++) {
for (let j = 1; j <= length2; j++) {
if (word1[i - 1] === word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(
dp[i - 1][j],
dp[i][j - 1],
dp[i - 1][j - 1]
) + 1;
}
}
}
return dp[length1][length2];
};
C:
int min(int num1, int num2, int num3) {
return num1 > num2 ? (num2 > num3 ? num3 : num2) : (num1 > num3 ? num3 : num1);
}
int minDistance(char * word1, char * word2){
int dp[strlen(word1)+1][strlen(word2)+1];
dp[0][0] = 0;
for (int i = 1; i <= strlen(word1); i++) dp[i][0] = i;
for (int i = 1; i <= strlen(word2); i++) dp[0][i] = i;
for (int i = 1; i <= strlen(word1); i++) {
for (int j = 1; j <= strlen(word2); j++) {
if (word1[i-1] == word2[j-1]) {
dp[i][j] = dp[i-1][j-1];
}
else {
dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1;
}
}
}
return dp[strlen(word1)][strlen(word2)];
}
Rust:
impl Solution {
pub fn min_distance(word1: String, word2: String) -> i32 {
let mut dp = vec![vec![0; word2.len() + 1]; word1.len() + 1];
for i in 1..=word2.len() {
dp[0][i] = i;
}
for (j, v) in dp.iter_mut().enumerate().skip(1) {
v[0] = j;
}
for (i, char1) in word1.chars().enumerate() {
for (j, char2) in word2.chars().enumerate() {
if char1 == char2 {
dp[i + 1][j + 1] = dp[i][j];
continue;
}
dp[i + 1][j + 1] = dp[i][j + 1].min(dp[i + 1][j]).min(dp[i][j]) + 1;
}
}
dp[word1.len()][word2.len()] as i32
}
}
One-dimensional dp
impl Solution {
pub fn min_distance(word1: String, word2: String) -> i32 {
let mut dp = vec![0; word1.len() + 1];
for (i, v) in dp.iter_mut().enumerate().skip(1) {
*v = i;
}
for char2 in word2.chars() {
// Simulating initialization of dp[i][0]
let mut pre = dp[0];
dp[0] += 1; // j = 0, transformation for the first i characters to an empty string
for (j, char1) in word1.chars().enumerate() {
let temp = dp[j + 1];
if char1 == char2 {
dp[j + 1] = pre;
} else {
dp[j + 1] = dp[j + 1].min(dp[j]).min(pre) + 1;
}
pre = temp;
}
}
dp[word1.len()] as i32
}
}