Edit Distance — Java Coding Problem
Difficulty: hard | Category: dynamic-programming
Problem 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 Input format: `word1|word2` **Constraints:** - `0 <= word1.length, word2.length <= 500` - `word1` and `word2` consist of lowercase English letters. **Hint:** Classic 2D DP — `dp[i][j]` is the edit distance between `word1[:i]` and `word2[:j]`.
Examples
Example 1
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: horse→rorse→rose→ros
Example 2
Input: word1 = "intention", word2 = "execution"
Output: 5