18-伪代码详解

4.4.4　伪代码详解

编辑距离求解函数：首先计算两个字符串的长度，然后从i=1开始，比较s₁[0]和s₂[]中的每一个字符，如果字符相等，diff[i][j]=0，否则diff[i][j]=1。因为这个值不需要记录，仅在公式表达时用数组表示，在程序设计时只用一个变量diff就可以了。

取上面+1（即d[i][j]=d[i−1][j]+1），左侧+1（即d[i][j]=d[i][j−1]+1），左上角数值+diff[i][j] （即d[i][j]=d[i−1][j−1]+ diff[i][j]）三者当中的最小值，相等时取后者。

直到i>len1时，算法结束，这时d[len1][len2]就是我们要的编辑距离。

int editdistance(char *str1, char *str2)
{
     int len1 = strlen(str1);      //计算字符串长度
     int len2 = strlen(str2); 
     for(int i=0;i<=len1;i++)      //当第二个串长度为0，编辑距离初始化为i
          d[i][0]= i;
     for(int j=0;j<=len2;j++)      //当第一个串长度为0，编辑距离初始化为j
          d[0][j]=j;
     for(int i=1;i <=len1;i++)     //遍历两个字符串
     {
          for(int j=1;j<=len2;j++)
          {
               int diff;//判断str[i]是否等于str2[j],相等为0，不相等为1
               if(str1[i-1] == str2[j-1]) //相等
                     diff = 0 ;
               else
                     diff = 1 ;
               int temp = min(d[i-1][j] + 1, d[i][j-1] + 1);//先两者取最小值
               d[i][j] = min(temp, d[i-1][j-1] + diff);//再取最小值，
                     //相当于三者取最小值d[i-1][j] + 1, d[i][j-1] + 1，d[i-1][j-1] + diff
          }
     }
     return d[len1][len2];
}