Preparing NOJ

编辑距离问题

1000ms 65536K

Description:

        AB2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括

(1)删除一个字符;

(2)插入一个字符;

(3)将一个字符改为另一个字符。

将字符串A变换为字符串B所用的最少字符操作数称为字符串AB的编辑距离,记为d(A,B)。试设计一个有效算法,对任给的2个字符串AB,计算出它们的编辑距离d(A,B)

对于给定的字符串A和字符串B,编程计算其编辑距离d(A,B)

Input:

输入数的第一行是字符串A,文件的第二行是字符串B

Output:

输出编辑距离d(A,B)的第1行中。

Sample Input:

fxpimu
xwrs

Sample Output:

5

Note:

undefined

本题由旧版NOJ导入,来源:算法设计与实验题解

Info

NOJ

Provider NOJ

Code NOJ1224

Tags

Submitted 2

Passed 2

AC Rate 100%

Date 04/20/2019 10:03:10

Related

Nothing Yet