Edit Distance

Return the minimum number of operations to turn the string a into b, where one operation is inserting a character, deleting a character or replacing a character.

For a = "horse" and b = "ros" the answer is 3 (horse -> rorse -> rose -> ros).

The starter code is a plain recursion. It is correct but too slow for long strings.

Examples

Example 1

Input:

edit_distance('horse', 'ros')

Output:

3

Example 2

Input:

edit_distance('intention', 'execution')

Output:

5

Constraints

• 0 <= len(a), len(b) <= 800
• Lower-case letters.