70. Edit Distance

HardString Dynamic Programming

Given two strings word1 and word2, return the minimum number of single-character edits needed to turn word1 into word2. The allowed edits are:

insert a character anywhere,
delete a character,
replace a character with a different one.

(This number is also known as the Levenshtein distance.)

Example 1

Input: word1 = "kitten", word2 = "sitting"
Output: 3

Explanation: Replace k with s (sitten), replace e with i (sittin), then insert g at the end.

Example 2

Input: word1 = "flaw", word2 = "lawn"
Output: 2

Explanation: Delete the leading f, then append n.

Example 3

Input: word1 = "", word2 = "abc"
Output: 3

Explanation: Insert all three characters.

Constraints

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

Follow-up: If only insertions and deletions were allowed (no replace), how does the answer relate to the longest common subsequence?

💡 Hint 1

Work on prefixes: let dp[i][j] be the distance between the first i characters of word1 and the first j of word2. Turning a prefix into the empty string takes i deletions (and j insertions the other way).

💡 Hint 2

If the last characters match, dp[i][j] = dp[i-1][j-1]. Otherwise the last edit was a replace, a delete or an insert: 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]).

💡 Hint 3

Only the previous row is needed, so the table can be reduced to O(n) space.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

DP on prefixes. dp[i][j] is the edit distance between word1[0..i) and word2[0..j). The borders are dp[i][0] = i (delete everything) and dp[0][j] = j (insert everything). For the rest: if word1[i-1] === word2[j-1], no edit is needed for that pair, so dp[i][j] = dp[i-1][j-1]. Otherwise take 1 plus the cheapest of replace (dp[i-1][j-1]), delete from word1 (dp[i-1][j]) or insert into word1 (dp[i][j-1]). Each row only depends on the previous one, so two rows suffice.

Time O(m · n)Space O(n)

function minDistance(word1, word2) {
  const n = word2.length;
  let prev = Array.from({ length: n + 1 }, (_, j) => j);
  let curr = new Array(n + 1).fill(0);
  for (let i = 1; i <= word1.length; i++) {
    curr[0] = i;
    for (let j = 1; j <= n; j++) {
      curr[j] = word1[i - 1] === word2[j - 1] ? prev[j - 1] : 1 + Math.min(prev[j - 1], prev[j], curr[j - 1]);
    }
    [prev, curr] = [curr, prev];
  }
  return prev[n];
}

class Solution {
    public int minDistance(String word1, String word2) {
        int n = word2.length();
        int[] prev = new int[n + 1], curr = new int[n + 1];
        for (int j = 0; j <= n; j++) prev[j] = j;
        for (int i = 1; i <= word1.length(); i++) {
            curr[0] = i;
            char a = word1.charAt(i - 1);
            for (int j = 1; j <= n; j++) {
                curr[j] = a == word2.charAt(j - 1) ? prev[j - 1] : 1 + Math.min(prev[j - 1], Math.min(prev[j], curr[j - 1]));
            }
            int[] t = prev; prev = curr; curr = t;
        }
        return prev[n];
    }
}

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
function minDistance(word1, word2) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit