DSA problem
Edit Distance
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, or replace a character.
This is the classic Levenshtein distance problem. It models a vast range of real-world tasks: spell checkers, DNA sequence alignment, diff utilities, and OCR correction all rely on this exact recurrence. The exponential brute force tries every possible edit sequence; dynamic programming collapses it to polynomial time by memoizing prefix distances.
Define dp[i][j] as the minimum number of operations to convert word1[0..i) into word2[0..j). The base cases capture pure inserts and deletes: dp[0][j] = j (insert j characters) and dp[i][0] = i (delete i characters). The recurrence has two cases: if word1[i-1] == word2[j-1], no operation is needed and dp[i][j] = dp[i-1][j-1]; otherwise pick the cheapest of insert, delete, replace:
dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) — corresponding to inserting word2[j-1], deleting word1[i-1], or replacing word1[i-1] with word2[j-1]. This runs in O(m * n) time and O(m * n) space, and since each row depends only on the previous row plus a diagonal, the space compresses naturally to O(min(m, n)).
Examples
word1 = "horse", word2 = "ros"3word1 = "intention", word2 = "execution"5word1 = "", word2 = "abc"3Constraints
- 0 <= word1.length, word2.length <= 500
- word1 and word2 consist of lowercase English letters.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.