计算字符串编辑距离

布满荆棘的人生 2022-08-06 17:26 248阅读 0赞

## 计算字符串编辑距离 ##

题目描述：给定两个字符串，要求二者之间的编辑距离。

**分析：**字符串的编辑主要有三种方式：增加、删除和修改。这道题目按照递归的方式，逐个判断每个字符。具体而言，如果str1和str2的第一个字符相等，则往后移，编辑的距离为后续的字符串；如果第一个不等，则我们可以增加、删除和修改str1，也可以增加、删除和修改str2，还可以同时增加、删除和修改str1和str2。不管以何种方式修改哪一个字符串，这个编辑距离都+1.

代码如下：

#include<iostream>
    #include<string>
    using namespace std; 
    
    int stringEditDistance(string str1, int begin1, int end1, string str2, int begin2, int end2)
    {
        if(begin1 > end1)
        {
            if(begin2 > end2)
                return 0; 
            else
                return end2 - begin2 + 1; 
        }
    
        if(begin2 > end2)
        {
            if(begin1 > end1)
                return 0; 
            else
                return end1 - begin1 + 1; 
        }
    
        if(str1[begin1] == str2[begin2])
        {
            return stringEditDistance(str1, begin1+1, end1, str2, begin2+1, end2); 
        }
        else
        {
            int dis1 = stringEditDistance(str1, begin1+1, end1, str2, begin2+2, end2); 
            int dis2 = stringEditDistance(str1, begin1+2, end1, str2, begin2+1, end2); 
            int dis3 = stringEditDistance(str1, begin1+2, end1, str2, begin2+2, end2); 
    
            if(dis1 <= dis2 && dis1 <= dis3)
                return dis1 + 1;
            if(dis2 <= dis1 && dis2 <= dis3)
                return dis2 + 1; 
            if(dis3 <= dis2 && dis3 <= dis1)
                return dis3 + 1; 
        }
    }
    
    int main()
    {
        string str1 = "ABCDE"; 
        string str2 = "ADBBDE"; 
    
        cout<<stringEditDistance(str1, 0, str1.length(), str2, 0, str2.length())<<endl; 
    
        return 0; 
    }

参考：  
《编程之美》