Fewest Edits Between Words

Medium2-D Dynamic Programming

Problem

A spell checker measures how far a typed word source is from a dictionary word target. One edit is inserting a character, deleting a character or replacing one character with another.

Return the minimum number of edits that turn source into target.

Example 1

Input:
source = "kitten", target = "mitten"
Output:
1

Replace the leading "k" with "m".

Example 2

Input:
source = "sunday", target = "saturday"
Output:
3

Insert "a" and "t" after "s", then replace "n" with "r".

Constraints

  • 0 ≤ source.length, target.length ≤ 500
  • Both strings contain lowercase English letters only.

Hint

Show the first hint

Work with prefixes: how many edits turn source[:i] into target[:j]?

Walkthrough

How to approach it

01Clarify before coding

  • Do all three operations cost 1? Yes.
  • Is a swap of two adjacent letters a single edit? No, only insert, delete and replace.
  • Can either word be empty? Yes: then the answer is the other word's length.

02Brute force

Recursively align the first characters: skip if equal, otherwise try insert, delete and replace and take the best.

Cost: O(3^(m + n)) without memoisation; hopeless for 500-character words.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.