Command Palette

Search for a command to run...

Hectal
Problem 31.4 · DP on Strings and SequencesMedium

Edit Distance

PatternDP on Two Strings

What it teaches: Three operations, three neighbours: replace (diagonal), delete (up), insert (left).

Practise it on judges as “Edit Distance”.

The problem

Return the minimum number of insertions, deletions and replacements to turn word1 into word2.

Example 1

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

horse → rorse → rose → ros.

Constraints

  • 0 ≤ lengths ≤ 500

Pattern clues in the wording

  • → Minimum edits between strings

These clues point to DP on Two Strings: dp[i][j] answers the question for the first i characters of one string and the first j of the other.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public int minDistance(String word1, String word2) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
word1 = "horse"
word2 = "ros"
3
2
word1 = "intention"
word2 = "execution"
5

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Levenshtein table · O(m × n)
1

Levenshtein table

Time O(m × n) Space O(m × n)

Fill (m + 1) × (n + 1); match copies the diagonal.

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

Verdict: The classic.

Before you submit

Edge cases and common mistakes

Test these inputs

  • One empty string
  • Identical strings (0)

Mistakes people make

  • Forgetting the base row and column.

Interview

Follow-up questions

How do spell checkers use this efficiently?