Edit Distance

描述

设A 和B 是2 个字符串。要用最少的字符操作将字符串A 转换为字符串B。这里所说的字符操作包括
(1)删除一个字符;
(2)插入一个字符;
(3)将一个字符改为另一个字符。
将字符串A变换为字符串B 所用的最少字符操作数称为字符串A到B 的编辑距离,记为d(A,B)。
试设计一个有效算法,对任给的2 个字符串A和B,计算出它们的编辑距离d(A,B)。

输入

第一行是字符串A,文件的第二行是字符串B。字符串长度不大于2000。

输出

输出距离d(A,B)

样例

  • Input
    fxpimu
    xwr
  • Output
    5

题解

  • dp[i][j]表示a的前i个字符到b的前j个字符的最优编辑距离
  • 从a到b
    • 删一个字符:dp[i][j]=dp[i-1][j]+1
    • 插入一个: dp[i][j]=dp[i][j-1]+1
    • 替换: dp[i][j]=dp[i-1][j-1]+1
    • a[i]==b[j]: dp[i][j]=dp[i-1][j-1]

      Code

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      #include<bits/stdc++.h>
      #define INIT(a,b) memset(a,b,sizeof(a))
      #define LL long long
      using namespace std;
      const int inf=0x3f3f3f3f;
      const int maxn=2e3+7;
      const int mod=1e9+7;
      int dp[maxn][maxn];
      int main(){
      char a[maxn],b[maxn];
      scanf("%s%s",a,b);
      int lena=strlen(a),lenb=strlen(b);
      for(int i=1;i<=lena;i++) dp[i][0]=i;
      for(int j=0;j<lenb;j++) dp[0][j]=j;
      for(int i=1;i<=lena;i++){
      for(int j=1;j<=lenb;j++){
      if(a[i-1]==b[j-1]) dp[i][j]=dp[i-1][j-1];
      else dp[i][j]=min(dp[i][j-1],min(dp[i-1][j],dp[i-1][j-1]))+1;
      }
      }
      printf("%d\n",dp[lena][lenb]);
      return 0;
      }
Donate comment here