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.Problem Overview: You are given two strings word1 and word2. The task is to compute the minimum number of operations required to convert word1 into word2. Allowed operations are insert, delete, and replace. This classic problem is known as Levenshtein Distance and heavily relies on dynamic programming over prefixes of the two strings.
Approach 1: Recursive Approach with Memoization (Time: O(m*n), Space: O(m*n))
Think of the problem as comparing characters starting from indices i in word1 and j in word2. If the characters match, move both pointers forward with no cost. If they differ, try the three valid operations: insert (advance j), delete (advance i), or replace (advance both). Each operation adds one step. The naive recursion explores an exponential number of states, but many subproblems repeat. Store results in a memo table keyed by (i, j). Memoization ensures each state is solved once, reducing time to O(m*n). This approach clearly expresses the decision process and works well when learning recursion on string problems.
Approach 2: Dynamic Programming Table (Time: O(m*n), Space: O(m*n))
Build a 2D DP table where dp[i][j] represents the minimum operations needed to convert the first i characters of word1 into the first j characters of word2. Initialize base cases: converting an empty string to length j requires j insertions, while converting length i to empty requires i deletions. Iterate through both strings and compare characters. If word1[i-1] == word2[j-1], carry over dp[i-1][j-1]. Otherwise compute 1 + min(insert, delete, replace) using dp[i][j-1], dp[i-1][j], and dp[i-1][j-1]. This bottom-up method systematically evaluates every prefix combination and avoids recursion overhead. It’s the standard approach for problems involving transformations between two strings.
The DP table can also be optimized to O(min(m,n)) space by storing only the current and previous rows since each state depends on adjacent rows. The time complexity remains O(m*n) because every pair of indices must still be evaluated.
Recommended for interviews: The bottom-up dynamic programming solution is what most interviewers expect. It demonstrates clear understanding of state definition, transitions, and base cases. Starting with the recursive reasoning helps explain the problem structure, but implementing the optimized DP table shows strong command of classic string transformation problems.
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.
This Python implementation uses dynamic programming. We start with initializing a table where each cell dp[i][j] represents the edit distance between the first i characters of word1 and the first j characters of word2.
The base cases are filled as follows: dp[i][0] = i (deleting all i characters of word1 to match an empty word2) and dp[0][j] = j (inserting all j characters of word2 into an empty word1).
We then populate the table by computing the cost of each edit operation and choosing the one with the minimum cost.
JavaScript
C
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.
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.
This Java solution implements a top-down recursion with memoization. The primary operation function 'helper' recursively solves the edit distance problem by considering character matches and operations separately.
Memoization is achieved by storing results of subproblems in a HashMap, uniquely keyed by the indices of remaining substrings.
C#
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.
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | 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. |
| Recursive Approach with Memoization | 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. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive with Memoization | O(m*n) | O(m*n) | When explaining the decision tree of insert/delete/replace or starting from a recursive formulation |
| Bottom-Up Dynamic Programming | O(m*n) | O(m*n) | Standard interview solution for transforming one string into another |
| Space Optimized DP | O(m*n) | O(min(m,n)) | When memory matters or strings are large |
Minimum Edit Distance Dynamic Programming • Tushar Roy - Coding Made Simple • 571,776 views views
Watch 9 more video solutions →Practice Edit Distance with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor