源字符串转变成目标字符串的编辑次数——动态规划方法实现

来源:互联网 发布:国密4算法的java实现 编辑:IT博客网 时间:2019/07/20 17:14

昨天看到一个算法面试题目,现与大家分享一下:

         给定一个源串和目标串,能够对源串进行如下操作:
          1.在给定位置上插入一个字符
          2.替换任意字符
          3.删除任意字符
 写一个程序,返回最小操作次数,使得对源串进行这些操作后等于目标串。源串和目标串的长度都小于2000。

分析:

       考虑源串”hello”,目标串”lleo”,则通过3次修改可以使得源串变成目标串(删除’h',删除’e',在’o'之前插入字符’e'),在此基础上我们可以想,采用动态规划的方法,假设f[i,j]表示源串S[0,1,2,.....i],变成D[0,1,2,.....j]进行的编辑次数,那我们可以列出状态方程:

f[i,j]=Min{f[i,j-1]+1,f[i-1,j]+1,f[i-1,j-1]+(S[i]==D[j]?0:1)}

其中:S[0,1,...i]经过f[i,j-1]次编辑变成D[0,1,....j-1]而,f[i,j-1]+1相当于,S[0,1,...i]经过f[i,j-1]次编辑变成D[0,1,....j-1]后再执行一次插入操作),同理,f[i-1,j]+1相当于,S[0,1,...i-1]经过f[i-1,j]次编辑变成D[0,1,....j]后,再执行一次删除操作;f[i-1,j-1]+(S[i]==D[j]?0:1)则根据,判断条件S[i]==D[j]来确定是否执行一次替换操作。废话不多说,直接上代码。

#include <stdio.h>#include <string.h>#include <stdlib.h>int Min(int left,int mid,int right){int temp = (left > mid) ? mid : left;return (temp > right) ? right : temp;}int Cal_Distance(const char *strS,const char *strD){size_t S_len,D_len;int *F;int i,j;int left,mid,right;int ret;if(strS==NULL || strD==NULL)return 0;S_len=strlen(strS);D_len=strlen(strD);F=malloc(sizeof(int)*((S_len+1)*(D_len+1)));if(F==NULL)printf("Out of space !");for(i=1,j=0; i<=S_len || j<=D_len; i++,j++){if(j <= D_len)*(F+j)=j;if(i <= S_len)*(F+i*(D_len+1))=i;}for(i=1; i<=S_len; i++){for(j=1; j<=D_len; j++){if(strS[i-1] == strD[j-1])right = *(F+(i-1)*(D_len+1)+j-1);elseright = *(F+(i-1)*(D_len+1)+j-1)+1;left = *(F+i*(D_len+1)+j-1)+1;mid = *(F+(i-1)*(D_len+1)+j)+1;*(F+i*(D_len+1)+j)=Min(left,mid,right);}}ret = *(F+(S_len+1)*(D_len+1)-1);free(F);return ret;}int main(){const char *strS="hello";const char *strD="lleo";int count;count=Cal_Distance(strS,strD);printf("edit counts: %d\n",count);}


0 0