⚠️ This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#72) before relying on it.

✏️ Edit Distance

An interactive visualization of how dynamic programming finds the minimum number of operations to convert one string to another. Watch the algorithm fill the DP table and compute the edit distance.

Dynamic Programming LeetCode 72 ↗ Medium

The 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

Interactive Visualization

Word 1

Word 2

Preset

Speed:

DP Table

Status

Press Step or Play to begin.

Code

fun minDistance(word1: String, word2: String): Int {    val m = word1.length; val n = word2.length    val dp = Array(m + 1) { IntArray(n + 1) }    for (i in 0..m)        dp[i][0] = i  // delete all    for (j in 0..n)        dp[0][j] = j  // insert all    for (i in 1..m) {        for (j in 1..n) {            if (word1[i - 1] == word2[j - 1])                dp[i][j] = dp[i - 1][j - 1]            else                dp[i][j] = 1 + minOf(                    dp[i - 1][j],      // delete                    dp[i][j - 1],      // insert                    dp[i - 1][j - 1]   // replace                )    } }    return dp[m][n]}

def minDistance(word1, word2):    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  # delete all    for j in range(n + 1):        dp[0][j] = j  # insert all    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-1][j],    # delete                    dp[i][j-1],    # insert                    dp[i-1][j-1]   # replace                )    return dp[m][n]

How It Works

Key Insight

The Edit Distance problem (also known as Levenshtein Distance) uses dynamic programming to build up the solution. We create a 2D table where dp[i][j] represents the minimum number of operations needed to convert the first i characters of word1 to the first j characters of word2.

The Three Operations

Insert: Add a character to word1. Cost: 1 + dp[i][j-1]
Delete: Remove a character from word1. Cost: 1 + dp[i-1][j]
Replace: Change a character in word1. Cost: 1 + dp[i-1][j-1]
Match: If characters are equal, no operation needed. Cost: dp[i-1][j-1]

The Recurrence

Base cases: dp[i][0] = i (delete all i characters) and dp[0][j] = j (insert all j characters).

For each cell dp[i][j]:
• If word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1]
• Otherwise: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

Complexity

Time O(m × n)

Space O(m × n)

We fill a table of size (m+1) × (n+1) where m and n are the lengths of the two strings. Each cell is computed in constant time by looking at three neighboring cells. The space complexity can be optimized to O(min(m, n)) by only keeping two rows at a time.