3-14 编辑距离

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

编辑距离

时间限制: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,共两次操作

2023年暑期算法队集训赛1

未参加
状态
已结束
规则
OI
题目
18
开始于
2023-07-06 09:00
结束于
2023-07-07 12:30
持续时间
27.5 小时
主持人
参赛人数
35