Fewest Letter Edits

Medium

You are given two strings source and target. A single edit does one of three things to source: - inserts any letter at any position; - deletes any letter; - replaces any letter with a different one. Return the smallest number of edits that turns source into target.

Example 1

source="table", target="cable" → 1

Replacing t with c is enough.

Example 2

source="sunday", target="saturday" → 3

Insert a and t after s, then replace n with r: 3 edits in total.

Example 3

source="", target="go" → 2

Two insertions turn the empty string into go.

Constraints

0 ≤ len(source), len(target) ≤ 500
Both strings consist of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Dynamic Programming

Similar problems

Longest Mirror Fragment Medium All Balanced Bracket Strings Medium Ways to Read a Digit Code Medium Weaving Two Strings Medium Cutting a Word Into Palindromes Medium

Input

source="table", target="cable"

Expected

Run checks the first 3 tests in your browser. Submit checks all 135 tests on the server, hidden ones included.