Problem statement

Given two strings word1 and word2, return the minimum number of operations to convert word1 into word2, where one operation inserts, deletes, or replaces a single character.

Example 1

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: horse → rorse → rose → ros.

Example 2

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

Constraints

• 0 <= word1.length, word2.length <= 15
• Lowercase English letters.

Hints for Edit Distance

1. Hint 1

   dp[i][j]: edits to turn the first i chars of word1 into the first j of word2.

2. Hint 2

   Equal last chars cost nothing; otherwise 1 + min(replace, delete, insert).

How to solve Edit Distance

Levenshtein distance. Let dp[i][j] be the cheapest way to turn the first i characters of word1 into the first j of word2. If the current characters agree, nothing needs doing and the cost carries over diagonally. If they differ, the last operation was an insert, a delete, or a replace — take the cheapest of those three and add one.

Approach

1. Base cases: turning a prefix into the empty string costs one delete per character, so dp[i][0] = i; symmetrically dp[0][j] = j.
2. If word1[i-1] == word2[j-1], set dp[i][j] = dp[i-1][j-1].
3. Otherwise dp[i][j] = 1 + min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]).
4. Those three terms are replace, insert and delete respectively.
5. Return dp[len1][len2].

Why it works

Every edit sequence can be reordered so operations apply left to right, which means the final operation on the last characters is one of exactly three kinds — and each leaves a smaller prefix pair to solve. The cases are exhaustive and each subproblem is independent of how it was reached, giving optimal substructure. When the characters already match, spending an operation can never help, so the diagonal carry is safe.

Complexity

• Time — O(len1 · len2)
• Space — O(len1 · len2)

Pitfalls

• The base row and column are i and j, not zeros — an empty target still costs one delete per character.
• Keep the three directions straight: diagonal is replace, left is insert, up is delete.
• On a match take the diagonal without adding one; adding one is the classic off-by-one here.
• Either word may be empty, and the base cases must cover that.

Reference solution

Python

def minDistance(word1: str, word2: str) -> int:
    n, m = len(word1), len(word2)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = i
    for j in range(m + 1):
        dp[0][j] = j
    for i in range(1, n + 1):
        for j in range(1, m + 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 - 1], dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]

Java

public static int minDistance(String word1, String word2) {
    int n1 = word1.length(), n2 = word2.length();
    int[][] dp = new int[n1 + 1][n2 + 1];
    for (int i = 0; i <= n1; i++) dp[i][0] = i;
    for (int j = 0; j <= n2; j++) dp[0][j] = j;
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
            else dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j]));
        }
    }
    return dp[n1][n2];
}

C++

int minDistance(string word1, string word2) {
    int n1 = (int) word1.size(), n2 = (int) word2.size();
    vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, 0));
    for (int i = 0; i <= n1; i++) dp[i][0] = i;
    for (int j = 0; j <= n2; j++) dp[0][j] = j;
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
            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 - 1], min(dp[i][j - 1], dp[i - 1][j]));
        }
    }
    return dp[n1][n2];
}

JavaScript

var minDistance = function(word1, word2) {
    const n = word1.length, m = word2.length;
    const dp = [];
    for (let i = 0; i <= n; i++) {
        dp.push(new Array(m + 1).fill(0));
        dp[i][0] = i;
    }
    for (let j = 0; j <= m; j++) dp[0][j] = j;
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            dp[i][j] = word1[i - 1] === word2[j - 1]
                ? dp[i - 1][j - 1]
                : 1 + Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[n][m];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Design a Food Rating System Medium
• Design Bitset Medium
• Iterator for Combination Medium
• Time Based Key-Value Store Medium
• Map Sum Pairs Medium
• Implement Magic Dictionary Medium