72. Edit distance

72_solution1_tab.c

#include <stdlib.h>
#include <string.h>

static int min3(int a, int b, int c) {
  int m = a < b ? a : b;
  return m < c ? m : c;
}

int minDistance(char *word1, char *word2) {
  int n = strlen(word1), m = strlen(word2);
  int w = m + 1;
  int *dp = malloc((n + 1) * w * sizeof(int)); // dp[i * w + j]

  for (int i = 0; i <= n; i++)
    dp[i * w] = i; // delete all
  for (int j = 0; j <= m; j++)
    dp[j] = j; // insert all

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (word1[i - 1] == word2[j - 1])
        dp[i * w + j] = dp[(i - 1) * w + (j - 1)];
      else
        dp[i * w + j] = 1 + min3(dp[(i - 1) * w + j],        // delete
                                 dp[i * w + (j - 1)],        // insert
                                 dp[(i - 1) * w + (j - 1)]); // replace
    }
  }
  int res = dp[n * w + m];
  free(dp);
  return res;
}

72_solution2_memo.c

#include <stdlib.h>
#include <string.h>

static const char *A, *B;
static int w;
static int *dp; // dp[i * w + j], -1 = not computed

static int min3(int a, int b, int c) {
  int m = a < b ? a : b;
  return m < c ? m : c;
}

static int f(int i, int j) {
  if (i == 0)
    return j; // insert the remaining j chars
  if (j == 0)
    return i; // delete the remaining i chars
  if (dp[i * w + j] != -1)
    return dp[i * w + j];

  if (A[i - 1] == B[j - 1])
    return dp[i * w + j] = f(i - 1, j - 1); // free match

  int del = f(i - 1, j);
  int ins = f(i, j - 1);
  int rep = f(i - 1, j - 1);
  return dp[i * w + j] = 1 + min3(del, ins, rep);
}

int minDistance(char *word1, char *word2) {
  int n = strlen(word1), m = strlen(word2);
  A = word1, B = word2, w = m + 1;
  dp = malloc((n + 1) * w * sizeof(int));
  for (int k = 0; k < (n + 1) * w; k++)
    dp[k] = -1;
  int res = f(n, m);
  free(dp);
  return res;
}

72_solution1_tab.cpp

#include <algorithm>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
  int minDistance(string word1, string word2) {
    int n = word1.size(), m = word2.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    for (int i = 0; i <= n; i++)
      dp[i][0] = i; // delete all
    for (int j = 0; j <= m; j++)
      dp[0][j] = j; // insert all

    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        if (word1[i - 1] == word2[j - 1])
          dp[i][j] = dp[i - 1][j - 1];
        else
          dp[i][j] = 1 + min({dp[i - 1][j],       // delete
                              dp[i][j - 1],       // insert
                              dp[i - 1][j - 1]}); // replace
      }
    }
    return dp[n][m];
  }
};

72_solution2_memo.cpp

#include <algorithm>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
  int f(int i, int j, string &a, string &b, vector<vector<int>> &dp) {
    if (i == 0)
      return j; // insert the remaining j chars
    if (j == 0)
      return i; // delete the remaining i chars
    if (dp[i][j] != -1)
      return dp[i][j];

    if (a[i - 1] == b[j - 1])
      return dp[i][j] = f(i - 1, j - 1, a, b, dp); // free match

    int del = f(i - 1, j, a, b, dp);
    int ins = f(i, j - 1, a, b, dp);
    int rep = f(i - 1, j - 1, a, b, dp);
    return dp[i][j] = 1 + min({del, ins, rep});
  }

  int minDistance(string word1, string word2) {
    int n = word1.size(), m = word2.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, -1));
    return f(n, m, word1, word2, dp);
  }
};

72_solution1_tab.go

package dp

func minDistance(word1 string, word2 string) int {
    n, m := len(word1), len(word2)
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, m+1)
    }

    for i := 0; i <= n; i++ {
        dp[i][0] = i // delete all
    }
    for j := 0; j <= m; j++ {
        dp[0][j] = j // insert all
    }

    for i := 1; i <= n; i++ {
        for j := 1; j <= m; j++ {
            if word1[i-1] == word2[j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                dp[i][j] = 1 + min(dp[i-1][j], // delete
                    dp[i][j-1],   // insert
                    dp[i-1][j-1]) // replace
            }
        }
    }
    return dp[n][m]
}

72_solution2_memo.go

package dp

func minDistance(word1 string, word2 string) int {
    n, m := len(word1), len(word2)
    dp := make([][]int, n+1) // -1 = not computed
    for i := range dp {
        dp[i] = make([]int, m+1)
        for j := range dp[i] {
            dp[i][j] = -1
        }
    }

    var f func(i, j int) int
    f = func(i, j int) int {
        if i == 0 {
            return j // insert the remaining j chars
        }
        if j == 0 {
            return i // delete the remaining i chars
        }
        if dp[i][j] != -1 {
            return dp[i][j]
        }

        if word1[i-1] == word2[j-1] {
            dp[i][j] = f(i-1, j-1) // free match
            return dp[i][j]
        }

        del := f(i-1, j)
        ins := f(i, j-1)
        rep := f(i-1, j-1)
        dp[i][j] = 1 + min(del, ins, rep)
        return dp[i][j]
    }

    return f(n, m)
}

72_solution1_tab.java

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

        for (int i = 0; i <= n; i++)
            dp[i][0] = i; // delete all
        for (int j = 0; j <= m; j++)
            dp[0][j] = j; // insert all

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = 1 + Math.min(dp[i - 1][j], // delete
                            Math.min(dp[i][j - 1], // insert
                                    dp[i - 1][j - 1])); // replace
            }
        }
        return dp[n][m];
    }
}

72_solution2_memo.java

import java.util.Arrays;

class Solution {
    private int f(int i, int j, String a, String b, int[][] dp) {
        if (i == 0)
            return j; // insert the remaining j chars
        if (j == 0)
            return i; // delete the remaining i chars
        if (dp[i][j] != -1)
            return dp[i][j];

        if (a.charAt(i - 1) == b.charAt(j - 1))
            return dp[i][j] = f(i - 1, j - 1, a, b, dp); // free match

        int del = f(i - 1, j, a, b, dp);
        int ins = f(i, j - 1, a, b, dp);
        int rep = f(i - 1, j - 1, a, b, dp);
        return dp[i][j] = 1 + Math.min(del, Math.min(ins, rep));
    }

    public int minDistance(String word1, String word2) {
        int n = word1.length(), m = word2.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int[] row : dp)
            Arrays.fill(row, -1);
        return f(n, m, word1, word2, dp);
    }
}

72_solution1_tab.js

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function (word1, word2) {
  const n = word1.length, m = word2.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(0));

  for (let i = 0; i <= n; i++) dp[i][0] = i; // delete all
  for (let j = 0; j <= m; j++) dp[0][j] = j; // insert all

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      if (word1[i - 1] === word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
      else
        dp[i][j] =
          1 +
          Math.min(
            dp[i - 1][j], // delete
            dp[i][j - 1], // insert
            dp[i - 1][j - 1], // replace
          );
    }
  }
  return dp[n][m];
};

72_solution2_memo.js

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function (word1, word2) {
  const n = word1.length, m = word2.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(-1));

  const f = (i, j) => {
    if (i === 0) return j; // insert the remaining j chars
    if (j === 0) return i; // delete the remaining i chars
    if (dp[i][j] !== -1) return dp[i][j];

    if (word1[i - 1] === word2[j - 1]) return (dp[i][j] = f(i - 1, j - 1)); // free match

    const del = f(i - 1, j);
    const ins = f(i, j - 1);
    const rep = f(i - 1, j - 1);
    return (dp[i][j] = 1 + Math.min(del, ins, rep));
  };

  return f(n, m);
};

72_solution1_tab.py

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n, m = len(word1), len(word2)
        dp = [[0] * (m + 1) for _ in range(n + 1)]

        for i in range(n + 1):
            dp[i][0] = i  # delete all
        for j in range(m + 1):
            dp[0][j] = j  # insert all

        for i in range(1, n + 1):
            for j in range(1, m + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = 1 + min(
                        dp[i - 1][j],  # delete
                        dp[i][j - 1],  # insert
                        dp[i - 1][j - 1],  # replace
                    )
        return dp[n][m]

72_solution2_memo.py

import sys


class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n, m = len(word1), len(word2)
        sys.setrecursionlimit(max(1000, 2 * (n + m) + 100))  # depth can reach n + m
        dp = [[-1] * (m + 1) for _ in range(n + 1)]

        def f(i: int, j: int) -> int:
            if i == 0:
                return j  # insert the remaining j chars
            if j == 0:
                return i  # delete the remaining i chars
            if dp[i][j] != -1:
                return dp[i][j]

            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = f(i - 1, j - 1)  # free match
                return dp[i][j]

            delete = f(i - 1, j)
            insert = f(i, j - 1)
            replace = f(i - 1, j - 1)
            dp[i][j] = 1 + min(delete, insert, replace)
            return dp[i][j]

        return f(n, m)

72_solution1_tab.rs

impl Solution {
    pub fn min_distance(word1: String, word2: String) -> i32 {
        let (a, b) = (word1.as_bytes(), word2.as_bytes());
        let (n, m) = (a.len(), b.len());
        let mut dp = vec![vec![0; m + 1]; n + 1];

        for i in 0..=n {
            dp[i][0] = i as i32; // delete all
        }
        for j in 0..=m {
            dp[0][j] = j as i32; // insert all
        }

        for i in 1..=n {
            for j in 1..=m {
                dp[i][j] = if a[i - 1] == b[j - 1] {
                    dp[i - 1][j - 1]
                } else {
                    1 + dp[i - 1][j] // delete
                        .min(dp[i][j - 1]) // insert
                        .min(dp[i - 1][j - 1]) // replace
                };
            }
        }
        dp[n][m]
    }
}

72_solution2_memo.rs

impl Solution {
    pub fn min_distance(word1: String, word2: String) -> i32 {
        let (a, b) = (word1.as_bytes(), word2.as_bytes());
        let mut dp = vec![vec![-1; b.len() + 1]; a.len() + 1];
        Self::f(a.len(), b.len(), a, b, &mut dp)
    }

    fn f(i: usize, j: usize, a: &[u8], b: &[u8], dp: &mut Vec<Vec<i32>>) -> i32 {
        if i == 0 {
            return j as i32; // insert the remaining j chars
        }
        if j == 0 {
            return i as i32; // delete the remaining i chars
        }
        if dp[i][j] != -1 {
            return dp[i][j];
        }

        dp[i][j] = if a[i - 1] == b[j - 1] {
            Self::f(i - 1, j - 1, a, b, dp) // free match
        } else {
            let del = Self::f(i - 1, j, a, b, dp);
            let ins = Self::f(i, j - 1, a, b, dp);
            let rep = Self::f(i - 1, j - 1, a, b, dp);
            1 + del.min(ins).min(rep)
        };
        dp[i][j]
    }
}