Minimum Edit Distance 2

Time limit2sMemory limit128 MB

Summary

Compute the minimum number of insert, delete, replace, and adjacent-swap operations to transform string X into string Y.

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

Problem

Given two strings X and Y, transform X into Y using the following edit operations. Each operation counts as one edit.

Insert: insert one lowercase English letter at any position in X.
Delete: delete one character from X.
Replace: replace one character of X with another lowercase English letter.
Swap: swap the positions of two adjacent characters in X.

Find the minimum number of edit operations needed to make X equal to Y.

Input

The first line contains string X, and the second line contains string Y. Each string has length between 1 and 1,000, inclusive, and consists only of lowercase English letters.

Output

Print the minimum number of edit operations needed to transform X into Y.

Examples1

Example 1
Input
```
abcdefg
abdecgcabf
```
Expected output
```
6
```