두 개의 문자열이 제공됩니다. 첫 번째 문자열은 소스 문자열이고 두 번째 문자열은 대상 문자열입니다. 이 프로그램에서 우리는 첫 번째 문자열을 두 번째 문자열로 변환하는 데 얼마나 많은 편집이 필요한지 찾아야 합니다.
문자열 편집은 일부 요소 삽입, 첫 번째 문자열에서 삭제 또는 두 번째 문자열로 변환할 항목 수정 중 하나일 수 있습니다.
입력 및 출력
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