Given two strings s1 and s2 of lengths m and n, find the minimum number of edits (operations) to convert "s1" into "s2" using operations of insert, remove or replace of a char.

Hint

This algorithm uses memoization to improve performance. It's same as the recursive version of Find the minimum number of edits, but with a special 'cache' to store results. The 'cache key' is crucial. It's how we identify and store past results. Sometimes we need one key, sometimes multiple keys. We add code to:

# Python implementation

cache = None

def count(s1, s2, i, j):
  if len(s1) <= 0:
    return len(s2)

  if len(s2) <= 0:
    return len(s1)

  global cache
  if not cache:
    cache = [[None] * len(s2) for _ in range(len(s1))]

  if not cache[i][j]:
    mn = 0

    if s1[0] == s2[0]:
      mn = count(s1[1:], s2[1:], i + 1, j + 1)
    else:
      mn = 1 + min(count(s1, s2[1:], i, j + 1), count(s1[1:], s2, i + 1, j), count(s1[1:], s2[1:], i + 1, j + 1))

    cache[i][j] = mn

  return cache[i][j]

s1 = 'sunday'
s2 = 'saturday'

print(count(s1, s2, 0, 0))

// Javascript implementation

let cache = null;

function count(s1, s2, i, j) {
  if (s1.length <= 0) {
    return s2.length;
  }

  if (s2.length <= 0) {
    return s1.length;
  }

  if (!cache) {
    cache = Array.from(Array(s1.length), () => Array(s2.length).fill(null));
  }

  if (!cache[i][j]) {
    let min = 0;

    if (s1.at(0) === s2.at(0)) {
      min = count(s1.slice(1), s2.slice(1), i + 1, j + 1);
    } else {
      min = 1 + Math.min(
        count(s1, s2.slice(1), i, j + 1),
        count(s1.slice(1), s2, i + 1, j),
        count(s1.slice(1), s2.slice(1), i + 1, j + 1)
      );
    }

    cache[i][j] = min;
  }

  return cache[i][j];
}

const s1 = 'sunday';
const s2 = 'saturday';

console.log(count(s1, s2, 0, 0));

Find the minimum number of edits (Memoization)

Hint