이 문제에서는 두 개의 문자열 str1과 str2가 제공됩니다. 우리의 임무는 한 문자열을 다른 문자열로 변환하는 가능한 모든 방법을 인쇄하는 프로그램을 만드는 것입니다.
문제 설명: 여기에서 str1을 str2로 변환할 수 있는 모든 가능한 방법을 찾아야 합니다. 변환하는 동안 세 가지 작업 중 하나를 수행할 수 있습니다.
- 삽입
- 제거
- 교체
문제를 이해하기 위해 예를 들어 보겠습니다.
입력: str1 ="kfeod" str2 ="kfcadq"
출력
Way1:
Insert q, after d. Replace c by e. Replace o by a.
솔루션 접근 방식
먼저 최소 편집 수를 찾은 다음 DP 매트릭스를 만듭니다. 그런 다음 두 문자열의 요소에 속하는 문자가 동일한지 확인한 다음 마지막 요소에서 복사하므로 수정하지 말고 그렇지 않으면 업데이트하십시오.
여기서 현재 문자 DP[i][j] =DP[i-1][j-1]입니다. str1의 (i-1)번째 요소와 str2의 (j-1)번째 요소가 같은지 확인하고 DP를 대각선으로 횡단합니다.
이제 str1의 (i-1)번째 요소와 str2의 (j-1)번째 요소가 같지 않은 경우. DP[i][j]의 값은 (DP[i-1][j-1] , DP[i][j-1] 및 DP[i-1][j] 중 최소값) + 1입니다.
이 메서드는 한 문자열을 다른 문자열로 변환하는 한 가지 방법을 인쇄할 수 있습니다. 모든 방법을 인쇄하는 방법은 문자열 벡터 와 같은 고급 데이터 구조를 사용하는 약간 까다롭습니다. 나중에 이에 대해 알아보겠습니다.
우리의 접근 방식의 작동을 설명하는 프로그램,
예시
#include <iostream>
using namespace std;
int DP[100][100];
void findWays(string str1, string str2) {
int len1 = str1.length();
int len2 = str2.length();
int i, j;
DP[len1 + 1][len2 + 1];
for (i = 0; i <= len1; i++)
DP[i][0] = i;
for (j = 0; j <= len2; j++)
DP[0][j] = j;
for (i = 1; i <= len1; i++) {
for (j = 1; j <= len2; j++) {
if (str1[i - 1] == str2[j - 1])
DP[i][j] = DP[i - 1][j - 1];
else
DP[i][j] = (min(min(DP[i - 1][j - 1], DP[i - 1][j]), DP[i][j - 1])) + 1;
}
}
while (len1 and len2) {
if (str1[len1 - 1] == str2[len2 - 1]) {
len1--;
len2--;
}
else if (DP[len1][len2] == DP[len1-1][len2-1] + 1) {
cout<<"\nModify '"<<str1[len1-1]<<"' to '"<<str2[len2-1];
len1--;
len2--;
}
else if (DP[len1][len2] == DP[len1-1][len2] + 1) {
cout<<"\nRemove "<<str1[len1-1]<<"'";
len1--;
}
else if (DP[len1][len2] == DP[len1][len2-1] + 1) {
cout <<"\nInsert '"<<str2[len2-1]<<"'";
len2--;
}
}
}
int main() {
string str1 = "kfeodge";
string str2 = "kfcadqpe";
cout<<"Way to convert one string into another string is ";
findWays(str1, str2);
return 0;
} 출력
Way to convert one string into another string is Modify 'g' to 'p Insert 'q' Modify 'o' to 'a Modify 'e' to 'c