Edit Distance

You can change a word with three kinds of edit: insert one character, delete one character, or replace one character with a different one. Write edit_distance(a, b) that returns the smallest number of edits that turns a into b.

Examples

edit_distance("sheep", "shop")      # returns 2
edit_distance("garden", "danger")   # returns 4
edit_distance("python", "pythons")  # returns 1
edit_distance("", "abc")            # returns 3

"sheep" becomes "shop" in two edits: delete one e, then replace the other e with an o.

Constraints

• 0 <= len(a), len(b) <= 500
• Both strings contain lowercase letters only