Final: Edit Distance

Lab Python Advanced 30 points

The edit distance between two words is the fewest single-letter changes – insert a letter, delete a letter, or replace a letter – that turn the first word into the second. Spell-checkers use it to suggest words. Print it.

Input

Two lines, one word each (at most 200 letters).

Output

One number.

Example

Input

horse
ros

Output

Sample input available Sample output available

Editor

Python

Hints

dp[i][j] = edits to turn the first i letters of a into the first j letters of b.

dp[i][0] = i (delete everything) and dp[0][j] = j (insert everything).

If the letters differ: 1 + min(delete, insert, replace).

Solution explanation

The same 2D table idea as LCS: O(n × m) time.

Show solution

a = input().strip()
b = input().strip()
dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(len(a) + 1):
    dp[i][0] = i
for j in range(len(b) + 1):
    dp[0][j] = j
for i in range(1, len(a) + 1):
    for j in range(1, len(b) + 1):
        if a[i - 1] == b[j - 1]:
            dp[i][j] = dp[i - 1][j - 1]
        else:
            dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
print(dp[len(a)][len(b)])

Output

Answer