Edit Distance

You may change a word with three kinds of edit, each counting as one: insert a letter, delete a letter, or replace a letter with another. Return the fewest edits that turn a into b.

Constraints

  • 0 ≤ length of a, length of b ≤ 500
  • a and b have lower-case English letters only.

Example 1

Input
a = "horse"
b = "ros"
Output
3
Why:

Replace h with r (rorse), delete r (rose), delete e (ros).

Example 2

Input
a = "intention"
b = "execution"
Output
5
Why:

For example: delete t, replace i with e, replace n with x, replace n with c, insert u.

Hints

    Was this a good challenge?

    Solved by
    0
    Submissions
    0
    Accepted
    –