Find the minimum number of edits

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 determines the minimum number of operations needed to make two strings identical.

• If the first characters of both strings match: The problem simplifies. We can safely remove the first character from both strings and continue the comparison with the remaining substrings.

• If the first characters of the strings differ, we explore three possible actions:

  • Remove the first character from the first string.
  • Remove the first character from the second string.
  • Remove the first character from both strings.

  The algorithm recursively calculates the minimum number of operations required for each of these choices. Finally, it selects the option that results in the fewest total operations.

In essence, the algorithm iteratively compares characters and makes the most efficient choices at each step to minimize the number of changes needed to make the strings identical.

• Python
• Javascript
•  Run

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

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

  mn = 0

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

  return mn

s1 = 'sunday'
s2 = 'saturday'

print(count(s1, s2))

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

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

  let min = 0;

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

  return min;
}

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

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