資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究編輯距離\n
給定兩個字串。第一個字串是源字串，第二個字串是目標字串。在這個程式中，我們必須找出將第一個字串轉換為第二個字串所需的可能編輯次數。
字串的編輯可以是插入一些元素、刪除第一個字串中的內容或修改一些內容以轉換為第二個字串。
輸入和輸出
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;
//when last character matches, recursively check previous characters
if (initStr[initLen-1] == finalStr[finalLen-1])
return editCount(initStr, finalStr, initLen-1, finalLen-1);
//if last character match is not found, check for insert, delete and update operations recursively
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
更新日期：16-6-2020
1K+ 瀏覽量
廣告