编辑距离
有两个字符串。第一个字符串是源字符串,第二个字符串是目标字符串。在此程序中,我们必须查找将第一个字符串转换为第二个字符串所需的编辑次数。
字符串的编辑可以是:插入一些元素,从第一个字符串中删除某些内容,或修改某些内容以转换为第二个字符串。
输入输出
Input: Two strings to compare. string 1: Programming string 2: Programs Output: Enter the initial string: Programming Enter the final string: Programs The number of changes required to convert Programming to Programs is 4
算法
editCount(initStr, finalStr, initLen, finalLen)
输入-初始和最终字符串及其长度。
输出-使initStr成为finalStr所需的编辑次数。
Begin if initLen = 0, then return finalLen if finalLen := 0, then return initLen if initStr[initLen - 1] = finalStr[finalLen - 1], then return editCount(initStr, finalStr, initLen – 1, finalLen - 1) answer := 1 + min of (editCount(initStr, finalStr, initLen , finalLen - 1)), (editCount(initStr, finalStr, initLen – 1, finalLen ), (editCount(initStr, finalStr, initLen – 1, finalLen - 1) return answer End
示例
#include<iostream> using namespace std; int min(int x, int y, int z) { //find smallest among three numbers if(x < y) { if(x < z) return x; else return z; }else { if(y < z) return y; else return z; } } int editCount(string initStr , string finalStr, int initLen, intfinalLen) { if (initLen == 0) //when initial string is empty, add all characters of final string return finalLen; if (finalLen == 0) //when final string is empty, delete all characters from initial string return initLen; //当最后一个字符匹配时,递归检查前一个字符 if (initStr[initLen-1] == finalStr[finalLen-1]) return editCount(initStr, finalStr, initLen-1, finalLen-1); //如果找不到最后一个字符,则递归检查插入,删除和更新操作 return 1 + min ( editCount(initStr, finalStr, initLen, finalLen- 1), // insert editCount(initStr, finalStr, initLen-1, finalLen), // delete editCount(initStr, finalStr, initLen-1, finalLen-1) // update ); } int main() { string initStr; string finalStr; cout << "Enter the initial string: "; cin >> initStr; cout << "Enter the final string: "; cin >> finalStr; cout << "The number of changes required to convert " << initStr << " to " << finalStr; cout << " is " << editCount( initStr , finalStr, initStr.size(), finalStr.size()) << endl; }
输出结果
Enter the initial string: Programming Enter the final string: Programs The number of changes required to convert Programming to Programs is 4