Edit Distance

Time: O(n*m)

Space: O(n*m)

Intuition

dp[i][j] = minimum edits to convert s1[0..i-1] to s2[0..j-1]. If characters match: dp[i][j]=dp[i-1][j-1]. Else: 1 + min(insert=dp[i][j-1], delete=dp[i-1][j], replace=dp[i-1][j-1]).

Algorithm

1dp[0][j]=j (j deletions), dp[i][0]=i (i insertions).
2For i,j from 1: if s1[i-1]==s2[j-1]: dp[i][j]=dp[i-1][j-1].
3Else: dp[i][j]=1+min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]).
4Return dp[m][n].

Example Walkthrough

Input: s1="sunday", s2="saturday"

1.dp table fills to give dp[6][8]=3 (insert a,t, replace n).

Output: 3

Common Pitfalls

•Three operations: insert (dp[i][j-1]+1), delete (dp[i-1][j]+1), replace (dp[i-1][j-1]+1).

Edit Distance.java

Java

// Approach: DP. dp[i][j] = minimum operations to convert s1[0..i-1] to s2[0..j-1].
// Transitions: match (0 cost), insert, delete, replace (each +1 cost).
// Time: O(n*m) Space: O(n*m)
import java.util.*;

class Solution {
    public int editDistance(String str1, String str2) {
        int n = str1.length();
        int m = str2.length();

        int[][] dp = new int[n][m];
        for (int[] row : dp)
            Arrays.fill(row, -1);

        return topDown(n - 1, m - 1, str1, str2, dp);
    }

    private int topDown(int i, int j, String s1, String s2, int[][] dp) {
        if (i < 0)
            return j + 1;

        if (j < 0)
            return i + 1;

        if (dp[i][j] != -1)
            return dp[i][j];

        if (s1.charAt(i) == s2.charAt(j))
            return dp[i][j] = topDown(i - 1, j - 1, s1, s2, dp);
        else
            return dp[i][j] = 1 + Math.min(topDown(i - 1, j - 1, s1, s2, dp),
                    Math.min(topDown(i - 1, j, s1, s2, dp), topDown(i, j - 1, s1, s2, dp)));
    }
}

Was this solution helpful?