Edit Distance

The key idea

Let dp[i][j] be the edit distance between the first i characters of word1 and the first j characters of word2. When the current characters match, no operation is needed and dp[i][j] = dp[i-1][j-1]. When they differ, take 1 + min of the three neighbors: delete (dp[i-1][j]), insert (dp[i][j-1]), or replace (dp[i-1][j-1]).

Problem

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:

- Insert a character
- Delete a character
- Replace a character

Constraints

0 <= word1.length, word2.length <= 500
word1 and word2 consist of lowercase English letters.

Examples

Input: word1 = "horse", word2 = "ros" Output: 3

Input: word1 = "intention", word2 = "execution" Output: 5

Complexity

Time: O(m*n) Space: O(m*n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →