题目描述

给定两个由小写英文字符组成的字符串 $s$ 和 $t$，请计算将 $s$ 修改成 $t$ 的最少操作次数。每次操作可以选择以下操作中的一种：

• 插入一个字符
• 删除一个字符
• 改变一个字符

这个最小操作次数又称为 $s$ 和 $t$ 的编辑距离。这是一个很重要的概念，比如：

• 微信公众号有个规定：已经发表的文章，只能修改 $20$ 个字。所以公众号的运营人员需要仔细计算新旧文章的编辑距离。
• DNA 是由 actg 四个字母组成的字符串，编辑距离可以规划编辑 DNA 的最佳方案。

输入格式

第一行：一个字符串 $s$，由小写英文字符组成 第二行：一个字符串 $t$，由小写英文字符组成

输出格式

单个整数：表示两个字符串的编辑距离

atcg
tcga

2

样例解释 1

删除第一个a，然后在字符串尾部再加一个a

abcdefg
gfedcba

6

数据范围

$1\leq |s|\leq 2000$ $1\leq |t|\leq 2000$