首页 > 代码库 > 洛谷 2758 编辑距离

洛谷 2758 编辑距离

题目描述

设A和B是两个字符串。我们要用最少的字符操作次数,将字符串A转换为字符串B。这里所说的字符操作共有三种:

1、删除一个字符;

2、插入一个字符;

3、将一个字符改为另一个字符;

!皆为小写字母!

输入输出格式

输入格式:

第一行为字符串A;第二行为字符串B;字符串A和B的长度均小于2000。

输出格式:

只有一个正整数,为最少字符操作次数。

输入输出样例

输入样例#1:
sfdqxbw                  
gfdgw
输出样例#1:
4

算法:DP

分析:
此题与P1279,求两个字符串的最长公共子串(不连续)算法相同。
使f[i,j]为s1的前i位转化成s2的前j为的最少步骤,
那么有动态转移方程:
 if s1[i]=s2[j] then f[i,j]:=f[i-1,j-1]//相同不用改动
 else
 f[i,j]:=min(f[i-1,j]//插入一个字符s2[j]
             f[i,j-1]//删除一个字符s1[i]
             f[i-1,j-1]//将s1[i]变为s2[j]
                )+1;//走一步
再加一个初始化即可。
题目不难,但这种思想可以广泛应用。

 

uses math;
var
 i,j,k,n,m,ans,num:longint;
 a:array[0..2000,0..2000] of longint;
 s,s1:ansistring;
begin
 readln(s); n:=length(s);
 readln(s1); m:=length(s1);
 for i:=1 to n do a[i,0]:=i;
 for i:=1 to m do a[0,i]:=i;
 for i:=1 to n do
  for j:=1 to m do
   begin
    if s[i]=s1[j] then
     begin a[i,j]:=a[i-1,j-1]; continue; end;
    a[i,j]:=min(min(a[i-1,j],a[i,j-1]),a[i-1,j-1])+1;
   end;
 writeln(a[n,m]);
end.

 

洛谷 2758 编辑距离