MediumStringDynamic Programming

Edit Distance

1 approach, code in every language

You are given two strings, word1 and word2. In a single operation you may insert one character, delete one character, or replace one character.

Return the minimum number of operations required to transform word1 into word2.

Example 1

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

Output: 3

Replace 'h' with 'r' to get rorse, delete 'r' to get rose, then delete 'e' to get ros. Three operations is the minimum.

Example 2

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

Output: 5

A minimal sequence uses one replace and several inserts and deletes to align the two words in five total edits.

Constraints

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

Two-Dimensional Prefix DP

Compute the edit distance between every pair of prefixes using a table with simple base cases.

Loading animation…

Intuition

Define dp[i][j] as the minimum number of operations to convert the first i characters of word1 into the first j characters of word2. Turning any prefix into the empty string costs one deletion per character, and building a prefix from the empty string costs one insertion per character, which fixes the base row and column as their own indices. When the current characters word1[i-1] and word2[j-1] are equal, no work is needed at this position, so dp[i][j] inherits dp[i-1][j-1]. When they differ, we take one operation plus the cheapest of three moves: an insert from dp[i][j-1], a delete from dp[i-1][j], or a replace from dp[i-1][j-1]. Filling the table in increasing order of i and j ensures each dependency is already computed.

Algorithm walkthrough

1Allocate a table of size (m + 1) by (n + 1) where m and n are the two string lengths.
2Initialize the first column with dp[i][0] = i and the first row with dp[0][j] = j to encode pure deletes and inserts.
3Scan i from 1 to m and j from 1 to n, filling each cell from its neighbors.
4If word1[i-1] equals word2[j-1], copy the diagonal value dp[i-1][j-1] with no added cost.
5Otherwise set dp[i][j] to 1 plus the minimum of the left, top, and diagonal cells for insert, delete, and replace.
6The bottom-right cell dp[m][n] is the minimum edit distance for the full strings.

Implementation

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m + 1):
            dp[i][0] = i
        for j in range(n + 1):
            dp[0][j] = j
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])
        return dp[m][n]

Time

O(m * n)

Space

O(m * n)

Each of the m by n cells is computed once from three neighbors. Space can be reduced to O(n) by keeping only the previous row, though the full table is easier to reason about.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Command Correction Cost is our own problem on the technique behind Edit Distance: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free