Crack the Backend

Problem Statement

Given two strings word1 and word2, return the minimum number of operations required to convert word1 into word2. You have three operations: insert a character, delete a character, or replace a character. Each operation counts as 1.

This is the classic Levenshtein distance. We need the minimum edits (insert/delete/replace) to turn word1 into word2.
Empty string: converting word1 to "" requires word1.length() deletes; converting "" to word2 requires word2.length() inserts.

Key Observations

Define dp[i][j] = minimum edits to convert word1[0..i) to word2[0..j). If word1[i-1] == word2[j-1], no edit needed for the last character: dp[i][j] = dp[i-1][j-1]. Otherwise we use one operation: replace (dp[i-1][j-1] + 1), delete from word1 (dp[i-1][j] + 1), or insert into word1 (dp[i][j-1] + 1). So dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]).
Base: dp[i][0] = i (delete all of word1[0..i)), dp[0][j] = j (insert all of word2[0..j)). Space can be optimized to one or two rows.

Approach

High-level: dp[i][j] = min edits to convert word1[0..i) to word2[0..j). If last chars match, dp[i][j] = dp[i-1][j-1]; else dp[i][j] = 1 + min(replace, delete, insert). Base: dp[i][0]=i, dp[0][j]=j.

Steps:

prev[j] = j for j = 0..n (row 0). For i = 1..m: cur[0] = i; for j = 1..n, if word1.charAt(i-1) == word2.charAt(j-1) then cur[j] = prev[j-1], else cur[j] = 1 + min(prev[j-1], prev[j], cur[j-1]). prev = cur.
Return prev[n].

Implementation

Java

public int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[] prev = new int[n + 1];

    for (int j = 0; j <= n; j++) {
        prev[j] = j;
    }

    for (int i = 1; i <= m; i++) {
        int[] cur = new int[n + 1];
        cur[0] = i;

        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1))
            cur[j] = prev[j - 1];
            else
            cur[j] = 1 + Math.min(prev[j - 1], Math.min(prev[j], cur[j - 1]));
        }

        prev = cur;
    }

    return prev[n];
}

Test Cases

Example 1

Input

word1 = "horse", word2 = "ros"

Expected

3

Explanation

horse -> rorse -> rose -> ros.

Complexity Analysis

Time: O(m*n).
Space: O(min(m,n)).

Follow-ups

Only allow insert and delete (no replace).