이 문제에서는 두 개의 문자열 str1과 str2가 주어집니다. 우리의 과제는 한 문자열을 다른 문자열로 변환하는 모든 가능한 방법을 출력하는 프로그램을 만드는 것입니다.
문제 설명
여기서 우리는 str1을 str2로 변환할 수 있는 모든 가능한 방법을 찾아야 합니다. 변환 과정에서 다음 세 가지 연산 중 하나를 수행할 수 있습니다.
- 삽입(Insert)
- 삭제(Remove)
- 교체(Replace)
예제로 문제 이해하기
입력: str1 = "kfeod", str2 = "kfcadq"
출력
방법1:
d 뒤에 q를 삽입합니다.
c를 e로 교체합니다.
o를 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이 됩니다.
이 방법은 한 문자열을 다른 문자열로 변환하는 하나의 방법만 출력할 수 있습니다. 모든 방법을 출력하는 방법은 문자열 벡터(vector of strings)와 같은 고급 자료구조를 사용해야 하므로 다소 까다롭습니다. 이에 대해서는 나중에 자세히 알아보겠습니다.
접근 방식의 동작을 보여주는 프로그램
예제 코드
#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
위 코드는 동적 계획법(DP) 테이블을 역추적하여 두 문자열 사이의 편집 거리를 만드는 데 사용된 삽입, 삭제, 교체 연산들을 출력합니다. 시간 복잡도는 O(m×n)이며, 여기서 m과 n은 각각 두 문자열의 길이입니다.