如果最后一个字符相同,那么最短的距离就是把最后一位去除后转换的最短的距离。如果不是最优,那么整体会有一个更优的解,因此当最后一位相等时,该问题具有最有子结构的形式;当最后一位不相等时,有如下三种情况:

  1. 将源串最后一位换成目标串最后一位,然后求源串除去最后一位以及目标串除去最后一位的最优编辑距离,总的最优编辑距离则在这基础上加一;
  2. 将源串末尾加上目标串最后一位,求源串除去最后一位而目标串除去最后一位的最优编辑距离,总距离在这基础上加一;
  3. 总距离为将源串去除最后一位后与目标串之间的最有编辑距离加一;

取以上三种情况的最小值,即为最短的编辑距离。设F[m][n]为源串的前m个字符转换到目标串的前n个字符所需要的最短编辑距离,源串为src,目标串为dst。那么有如下公式:

F[0][0]=0 if src[0]==dst[0]
F[0][0]=1 if src[0]!=dst[0]

F[0][n]=n if src[0]==dst[n]
F[0][n]=F[0][n-1]+1 if src[0]!=dst[n]
F[m][0]=m if src[m]==dst[0]
F[m][0]=F[m-1][0]+1 if src[m]!=dst[0]

F[m][n]=F[m-1][n-1] if src[m]==dst[n]
F[m][n]=min(F[m-1][n-1]+1,F[m][n-1]+1,F[m-1][n]+1) if src[m]!=dst[n]

公式出来编程就简单了,从F[0][0]遍历到F[M-1][N-1]即可,其中,MN分别是源串与字串的长度,最后的结果就是F[M-1][N-1]的结果了,时间复杂度为O(M*N)

#include<fstream>
#include<string>
#include<iostream>
using namespace std;

int min(int a,int b)
{
  if(a<b)
  {
    return a;
  }else
  {
    return b;
  }
}

int main()
{
  const int MAXM=1002;
  const int MAXN=1002;
  
  ifstream fIn("input.txt");
  ofstream fOut("output.txt");
  string src="",dst="";
  fIn>>src;fIn>>dst;
  
  int F[MAXM][MAXN];
  for(int i=0;i<src.length();i++)
  {
    for(int j=0;j<dst.length();j++)
    {
      if(i==0 && j==0)
      {
        if(src[i]==dst[j])
        {
          F[i][j]=0;
        }else
        {
          F[i][j]=1;
        }
      }else if(i==0)
      {
        if(src[i]==dst[j])
        {
          F[i][j]=j;
        }else
        {
          F[i][j]=F[i][j-1]+1;
        }
      }else if(j==0)
      {
        if(src[i]==dst[j])
        {
          F[i][j]=i;
        }else
        {
          F[i][j]=F[i-1][j]+1;
        }
      }else
      {
        if(src[i]==dst[j])
        {
          F[i][j]=F[i-1][j-1];
        }else
        {
          F[i][j]=min(min(F[i-1][j-1]+1,
                          F[i][j-1]+1),
                          F[i-1][j]+1);
        }
      }
    }
  }
  fOut<<F[src.length()-1][dst.length()-1]<<endl;
  
  return 0;
}