Minimum edit

Interview

Time limit2sMemory limit512 MB

Summary

Compute the Levenshtein distance between two lowercase strings, using the fewest insert, delete, and replace operations to change A into B.

Level: Medium6 of 10
Topics: Dynamic programming, String, Array, Prefix sum
Solved: No attempts yet

Problem

Given two strings $A$ and $B$ , the task of turning $A$ into $B$ with the fewest operations is called the minimum edit problem.

Three operations apply to $A$ .

Insert: put one character at any position of $A$ .
Delete: remove one character of $A$ .
Replace: change one character of $A$ into another character.

Given the two strings, write a program that computes the minimum number of edits.

Input

The first line has the string $A$ and the second line has the string $B$ . Both strings consist of lowercase letters only, and neither is longer than 1000 characters.

Output

Print on the first line the minimum number of edits that turn $A$ into $B$ .

Examples10

Example 1
Input
```
abc
ab
```
Expected output
```
1
```
Example 2
Input
```
ca
abc
```
Expected output
```
3
```
Example 3
Input
```
abc
cba
```
Expected output
```
2
```
Example 4
Input
```
abcd
bcde
```
Expected output
```
2
```
Example 5
Input
```
abababababa
aaaaaaaaaaa
```
Expected output
```
5
```
Example 6
Input
```
for
whileforif
```
Expected output
```
7
```
Example 7
Input
```
whilewhile
whalewhale
```
Expected output
```
2
```
Example 8
Input
```
aaabaaa
acacaca
```
Expected output
```
3
```
Example 9
Input
```
qwerty
dvorak
```
Expected output
```
5
```
Example 10
Input
```
asdf
asdf
```
Expected output
```
0
```