Find the minimum number of single-character edits needed to transform one string into another.
Given two strings word1 and word2, compute the minimum number of operations required to change word1 into word2.
You may perform any of the following operations on a string:
- Insert one character
- Delete one character
- Replace one character
Each operation costs 1. Return the smallest total cost to make the strings equal.
Input Format
- Two strings
word1andword2. - Each string contains lowercase English letters in the standard formulation of the problem.
Output Format
- Return one integer: the minimum edit distance between
word1andword2.
Constraints
- The answer is a non-negative integer.
- Standard interview formulation assumes strings may be empty.
- A dynamic programming solution is expected for the general case.
Example 1
Input
word1 = "horse", word2 = "ros"
Output
3
Explanation
One optimal sequence is: horse -> rorse (replace 'h' with 'r') -> rose (delete 'r') -> ros (delete 'e').
Example 2
Input
word1 = "intention", word2 = "execution"
Output
5
Explanation
A minimum-cost sequence uses 5 edits to transform the first string into the second.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.