{x}
blog image

Edit Distance

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:

  • 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.

Solution Explanation: Edit Distance

The problem asks for the minimum number of operations (insert, delete, replace) needed to transform word1 into word2. This is a classic dynamic programming problem.

Approach: Dynamic Programming

We use a 2D array dp where dp[i][j] represents the minimum edit distance between the first i characters of word1 and the first j characters of word2.

Base Cases:

  • dp[i][0] = i for all i: To transform the first i characters of word1 to an empty string, we need i deletions.
  • dp[0][j] = j for all j: To transform an empty string to the first j characters of word2, we need j insertions.

Recursive Relation:

For i > 0 and j > 0, we have three possibilities:

  1. word1[i-1] == word2[j-1]: If the last characters are the same, we don't need any operation, so dp[i][j] = dp[i-1][j-1].
  2. word1[i-1] != word2[j-1]: We have three choices:
    • Insert: Insert word2[j-1] into word1, costing 1 operation. dp[i][j] = dp[i][j-1] + 1.
    • Delete: Delete word1[i-1] from word1, costing 1 operation. dp[i][j] = dp[i-1][j] + 1.
    • Replace: Replace word1[i-1] with word2[j-1], costing 1 operation. dp[i][j] = dp[i-1][j-1] + 1. We choose the minimum of these three options: dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1.

Final Result:

The final answer is dp[m][n], where m and n are the lengths of word1 and word2 respectively.

Time and Space Complexity:

  • Time Complexity: O(m*n), where 'm' and 'n' are the lengths of the input strings. We iterate through the dp array once.
  • Space Complexity: O(mn). We use a 2D array of size (m+1) x (n+1) to store the dp values. This can be optimized to O(min(m,n)) using space optimization techniques, but the provided solutions use the simpler O(mn) space approach for better readability.

Code in different languages

The code implementations in Python, Java, C++, Go, TypeScript, and Javascript are provided in the original response and follow the dynamic programming approach explained above. Each implementation efficiently calculates the dp table and returns the final result. The minor differences are due to the syntax and library functions specific to each language.