编辑距离

时间限制：1s

空间限制：256MB

Description

这是一个非常经典的问题，对于给定的两个字符串，求最小操作数使两个字符串相同。

对于操作一次我们是这样定义的：

1.插入：向一个字符串中插入一个字符

2.修改：将字符串中的一个字符替换成另一个字符

3.删除：将字符串的一个字符删除

给出两个字符串，该如何求解其最小操作数，即最小编辑距离

Input Format

第一行输入字符串t1，第二行输入字符串t2

Output Format

输出一个整数，表示最小编辑距离

Data Range

• \(0\leq  t1，t2\leq 4999\)

Input Example #1：

math
mouth

Output Example #1：

2

Input Example #2：

math
    

Output Example #2：

4

Note

说明：样例1，将a换成0，moth中插入u，共两次操作