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:
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 <= 500word1 and word2 consist of lowercase English letters.The Edit Distance problem asks for the minimum number of operations required to convert one string into another. Allowed operations typically include insert, delete, and replace. Because many subproblems repeat when comparing prefixes of the two strings, this problem is best approached using Dynamic Programming.
A common strategy is to build a dp table where dp[i][j] represents the minimum operations required to convert the first i characters of one string into the first j characters of the other. By comparing characters and considering the three possible operations, you iteratively fill the table from smaller prefixes to larger ones. Base cases handle transformations involving empty prefixes.
This approach efficiently reuses previously computed results, leading to a time complexity of O(m × n), where m and n are the lengths of the two strings. Space can also be optimized using rolling arrays.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming (2D DP table) | O(m × n) | O(m × n) |
| Space Optimized DP | O(m × n) | O(min(m, n)) |
Tushar Roy - Coding Made Simple
This approach uses a 2D array to store the edit distances between all prefixes of both strings. By building solutions for smaller subproblems, we can efficiently calculate the solution for the entire problem.
We define dp[i][j] as the edit distance between the first i characters of word1 and the first j characters of word2. The recursion is based on comparing the last characters of the current substrings. If they are the same, the edit distance is the same as dp[i-1][j-1], otherwise, we add 1 (to account for an edit operation) and consider the minimum edit distance found after each possible operation: insertion, deletion, or replacement.
Time Complexity: O(m * n) where m and n are the lengths of word1 and word2 respectively, as we compute values for each combination of indices.
Space Complexity: O(m * n) for storing the dp table.
1function minDistance(word1, word2) {
2 const m = word1.length;
3 const n = word2.length;
4 const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
5
6 for (let i = 0; i <= m; ++i) {
7 dp[i][0] = i;
8 }
9 for (let j = 0; j <= n; ++j) {
10 dp[0][j] = j;
11 }
12
13 for (let i = 1; i <= m; ++i) {
14 for (let j = 1; j <= n; ++j) {
15 if (word1[i - 1] === word2[j - 1]) {
16 dp[i][j] = dp[i - 1][j - 1];
17 } else {
18 dp[i][j] = 1 + Math.min(
19 dp[i - 1][j], // delete
20 dp[i][j - 1], // insert
21 dp[i - 1][j - 1] // replace
22 );
23 }
24 }
25 }
26
27 return dp[m][n];
28}This JavaScript function mirrors the dynamic programming approach used in the Python solution. A 2D array dp is created to store the edit distances.
We iterate over the lengths of the strings, filling out the dp table according to whether characters match or not, updating the distances according to delete, insert, and replace operations.
This approach uses recursive calls with memoization to effectively reduce the factors of redundant subproblem calculations. We use a hash map or an array to store results of previously encountered subproblems to avoid recalculating them, subsequently turning the recursive depth-first search into a memoized search.
Time Complexity: O(m * n) where m and n are lengths of word1 and word2. Each subproblem is computed once.
Space Complexity: O(m * n) for memoization storage plus recursion call stack space.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 private Dictionary<(int, int), int> memo = new Dictionary<(int, int), int>();
public int MinDistance(string word1, string word2) {
return MinDistanceHelper(word1, word2, word1.Length, word2.Length);
}
private int MinDistanceHelper(string word1, string word2, int m, int n) {
if (memo.ContainsKey((m, n))) {
return memo[(m, n)];
}
if (m == 0) return n;
if (n == 0) return m;
if (word1[m - 1] == word2[n - 1]) {
memo[(m, n)] = MinDistanceHelper(word1, word2, m - 1, n - 1);
} else {
int insert = MinDistanceHelper(word1, word2, m, n - 1);
int delete = MinDistanceHelper(word1, word2, m - 1, n);
int replace = MinDistanceHelper(word1, word2, m - 1, n - 1);
memo[(m, n)] = 1 + Math.Min(insert, Math.Min(delete, replace));
}
return memo[(m, n)];
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Edit Distance is a classic dynamic programming problem frequently discussed in technical interviews, including FAANG-level companies. It tests understanding of DP transitions, string manipulation, and optimization techniques.
The optimal approach uses dynamic programming. A 2D DP table stores the minimum operations needed to convert prefixes of one string into prefixes of another, avoiding repeated computation and ensuring efficient processing.
The problem has overlapping subproblems and optimal substructure. Converting larger prefixes depends on results from smaller prefixes, which makes storing intermediate results with dynamic programming very effective.
Most solutions use a 2D array (DP table) where each cell represents the minimum edit operations for specific prefix lengths. Some optimized solutions reduce memory by using two 1D arrays instead of the full matrix.
The C# solution uses recursion with a Dictionary for memoization. The approach efficiently prevents duplicate calculations by storing previously computed edit distances as key-value pairs, where the key is a tuple of current substring indices.
By breaking the problem into subproblems based on recursive function calls, it ensures that computed data is reused whenever the same indices are encountered.