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,共两次操作