Edit Distance
Given two strings word1 and word2, return the minimum number of operations required to convert word1 into word2.
You may perform the following operations:
- Insert one character.
- Delete one character.
- Replace one character with another character.
Example 1
Input
word1 = "horse" word2 = "ros"
Output
3
Explanation
One way to convert "horse" into "ros" is:
horse → rorse
rorse → rose
rose → ros
The operations are:
- Replace h with r
- Delete r
- Delete e
Therefore, the minimum number of operations is 3.
Example 2
Input
word1 = "intention" word2 = "execution"
Output
5
Explanation
One optimal sequence is:
intention → inention
inention → enention
enention → exention
exention → exection
exection → execution
This requires 5 operations.
Constraints
Hints:
Hint 1
Let dp[i][j] represent the minimum operations required to convert the first i characters of word1 into the first j characters of word2.
Hint 2
If the current characters are equal:
word1[i - 1] == word2[j - 1]
then no new operation is required:
dp[i][j] = dp[i - 1][j - 1]
Author & Technical Reviewer
Technically reviewed by: ExamAdda Technical Review Team
Technical Reviewers, ExamAdda
Software engineers at ExamAdda who check every article's definitions, complexity claims and code examples before and after publishing.
Published
Aug 24, 2026
Last updated
Aug 24, 2026
Content Verification Methodology
Definitions and complexity claims were checked against authoritative computer-science references. Code examples were compiled and tested with standard, boundary and edge-case inputs.
Expected Output