Edit Distance
HardStringDynamic ProgrammingGreedyMath
Description
Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. You have three operations: Insert a character, Delete a character, Replace a character.
Examples
Input:
word1 = "horse", word2 = "ros"Output:
3Explanation:
Horse -> rorse (replace 'h' with 'r') -> rose (remove 'r') -> ros (remove 'e')
Input:
word1 = "intention", word2 = "execution"Output:
5Explanation:
Intention -> inention -> enention -> exention -> exection -> execution
Input:
word1 = "", word2 = "a"Output:
1Explanation:
Empty word1 requires 1 insertion to become a. DP base case: edit distance = target length.
Constraints
- •
0 ≤ word1.length, word2.length ≤ 500 - •
word1 and word2 consist of lowercase English letters.
Ready to solve this problem?
Practice solo and sharpen your skills for technical interviews.