Spelling Test Fixes

Harddynamic programmingAlso known as Edit Distance (Levenshtein Distance)

A primary-school teacher marks weekly spelling tests. Instead of a plain right or wrong, she gives each word a "fixes" score: the smallest number of single-letter fixes that turn the child's attempt into the correct word. A fix is adding one letter, removing one letter, or changing one letter into another.

A score of 1 means "so close", and a big score means "let's practise this one". Marking thirty tests by hand is slow, so she wants a program to work out the score.

Your task

Write fewestFixes(attempt, word). Return the smallest number of fixes that turn attempt into word, where each fix inserts one letter anywhere, deletes one letter, or replaces one letter with a different letter.

If the two strings are already equal, return 0. Either string may be empty.

fewestFixes(attempt: string, word: string) → int

Examples

Example 1

Input

attempt = "recieve"
word = "receive"

Output

Why

Change the i to e and the e after it to i: 2 fixes. There is no 1-fix answer, because the strings differ in two positions and have the same length, so one insert or delete cannot help.

Example 2

Input

attempt = "nite"
word = "night"

Output

Why

Keep n, i and t. Add g and h before the t, then remove the final e: n, i, +g, +h, t, -e. That is 3 fixes, and no shorter list of fixes works.

Constraints

0 ≤ attempt.length, word.length ≤ 500
Both strings contain only lowercase letters a to z.

Start with brute force

Explore every sequence of fixes, for example with breadth-first search over all strings reachable in 1 fix, then 2, and so on. Each string has hundreds of neighbours (26 letters to insert at each gap, plus deletes and replaces), so after a few levels there are billions of strings.

A recursive version of the last-letter rule is much smaller but still exponential, because it reaches the same pair of prefixes along many different paths. With 500-letter strings that is hopeless without a table.

Hints

0 of 4 shown

Hint 1
Compare frend and friend letter by letter from the left. How many positions differ? Now, how many fixes does it really take? What does that tell you about lining the letters up position by position?
Hint 2
One missing letter shifts everything after it, so you cannot fix positions independently. Look at the last letters instead. If they are equal, they need no fix: the score is the score of both strings without them. If not, the last fix involves them somehow.
Hint 3
If the last letters differ, there are three options: replace the attempt's last letter with the word's (then solve both shorter by one), delete the attempt's last letter (attempt shorter by one), or insert the word's last letter at the end (word shorter by one). Take the cheapest and add 1.
Hint 4
Let fix[i][j] be the score for the first i letters of attempt and the first j of word. The first row is j (insert everything) and the first column is i (delete everything). Fill row by row: diagonal if the letters match, else 1 + min(diagonal, above, left).

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

Work on prefixes and look only at the last letters. If they match, keep them for free. If not, the cheapest plan ends with one of three fixes, each leaving a smaller pair of prefixes: replace (both shrink), delete (the attempt shrinks), insert (the word shrinks). Each cell of a table holds the score for one pair of prefixes.

Trace "cut" into "cat". Rows are prefixes of the attempt, columns prefixes of the word:

	(empty)	c	a	t
(empty)	0	1	2	3
c	1	0	1	2
u	2	1	1	2
t	3	2	2	1

Row "c", column "c": the letters match, copy the diagonal: 0.
Row "u", column "a": u ≠ a, so 1 + min(diagonal 0, above 1, left 1) = 1. That is the replace u → a.
Row "t", column "t": t matches t, copy the diagonal (row "u", column "a"): 1.

The answer, bottom-right, is 1. The edges of the table are the base cases: turning a prefix into the empty string costs one delete per letter, and building a prefix from nothing costs one insert per letter.

Reference solution

function fewestFixes(attempt, word) {
  const m = word.length;
  // prev[j] = fixes for the previous prefix of attempt and word[0..j)
  let prev = Array.from({ length: m + 1 }, (_, j) => j); // empty attempt: insert j letters
  for (let i = 1; i <= attempt.length; i++) {
    const cur = [i]; // empty word: delete i letters
    for (let j = 1; j <= m; j++) {
      if (attempt[i - 1] === word[j - 1]) cur[j] = prev[j - 1]; // last letters match
      else cur[j] = 1 + Math.min(
        prev[j - 1], // replace
        prev[j],     // delete from attempt
        cur[j - 1]   // insert into attempt
      );
    }
    prev = cur;
  }
  return prev[m];
}

def fewest_fixes(attempt, word):
    m = len(word)
    # prev[j] = fixes for the previous prefix of attempt and word[:j]
    prev = list(range(m + 1))  # empty attempt: insert j letters
    for i in range(1, len(attempt) + 1):
        cur = [i] + [0] * m  # empty word: delete i letters
        for j in range(1, m + 1):
            if attempt[i - 1] == word[j - 1]:
                cur[j] = prev[j - 1]  # last letters match
            else:
                cur[j] = 1 + min(prev[j - 1],  # replace
                                 prev[j],      # delete from attempt
                                 cur[j - 1])   # insert into attempt
        prev = cur
    return prev[m]

TimeO(n × m)Each of the (n + 1) × (m + 1) cells takes constant time.

SpaceO(m)Only the previous row and the current row are kept.

Learn the idea: DP on Strings Strings

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code