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 <= 500
word1
and word2
consist of lowercase English letters.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.
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:
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]
.word1[i-1] != word2[j-1]
: We have three choices:
word2[j-1]
into word1
, costing 1 operation. dp[i][j] = dp[i][j-1] + 1
.word1[i-1]
from word1
, costing 1 operation. dp[i][j] = dp[i-1][j] + 1
.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.
dp
array once.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.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.