Edit Distance

medium dp string

Problem

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. You have the following three operations permitted on a word: Insert a character Delete a character Replace a character

Inputa = "cake", b = "make"

Output1

Replace 'c' with 'm'.

def edit_distance(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1): dp[i][0] = i
    for j in range(n + 1): dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[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[m][n]

function editDistance(a, b) {
  const m = a.length, n = b.length;
  const dp = Array.from({ length: m + 1 }, (_, i) =>
    Array.from({ length: n + 1 }, (_, j) => (i === 0 ? j : (j === 0 ? i : 0))));
  for (let i = 1; i <= m; i++) for (let j = 1; j <= n; j++) {
    if (a[i - 1] === b[j - 1]) dp[i][j] = dp[i - 1][j - 1];
    else dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]);
  }
  return dp[m][n];
}

class Solution {
    public int editDistance(String a, String b) {
        int m = a.length(), n = b.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++) {
            if (a.charAt(i - 1) == b.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 - 1][j], dp[i][j - 1]));
        }
        return dp[m][n];
    }
}

int editDistance(string a, string b) {
    int m = a.size(), n = b.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    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++) {
        if (a[i - 1] == b[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[m][n];
}

Explanation

Edit distance asks for the fewest insert, delete, and replace operations to turn one word into another. We solve it with a 2D DP where dp[i][j] is the minimum edits to convert the first i chars of a into the first j chars of b.

The first row and column are the easy cases: turning a prefix into the empty string (or vice versa) costs exactly its length, so dp[i][0] = i and dp[0][j] = j.

For the rest, if the current characters match, nothing needs doing and we inherit dp[i-1][j-1]. If they differ, we take 1 + the best of three choices: replace (dp[i-1][j-1]), delete (dp[i-1][j]), or insert (dp[i][j-1]).

Example: a = "cake", b = "make". Only the first letters differ, so one replace ('c' → 'm') is enough and the answer is 1.

The final answer sits at dp[m][n]. We fill the whole m × n table with constant work per cell, so the cost is proportional to m · n.

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