Trong bài toán này, chúng ta được cung cấp hai chuỗi str1 và str2. Nhiệm vụ của chúng ta là tạo một chương trình để In tất cả các cách có thể để chuyển đổi một chuỗi này thành một chuỗi khác.
Mô tả sự cố: Ở đây, chúng ta cần tìm tất cả các cách có thể sử dụng mà chúng ta có thể chuyển đổi str1 thành str2. Trong khi chuyển đổi, chúng tôi có thể thực hiện bất kỳ thao tác nào trong ba thao tác,
- Chèn
- Xóa
- Thay thế
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào: str1 =“kfeod” str2 =“kfcadq”
Đầu ra
Way1:
Insert q, after d. Replace c by e. Replace o by a.
Phương pháp tiếp cận giải pháp
Chúng tôi sẽ tìm số lượng chỉnh sửa tối thiểu trước tiên và sau đó tạo một ma trận DP. Sau đó, kiểm tra xem ký tự liên quan đến phần tử trong cả hai chuỗi có bằng nhau hay không, sau đó không sửa đổi nếu không, hãy cập nhật vì nó được sao chép từ phần tử cuối cùng.
Ở đây, ký tự hiện tại DP [i] [j] =DP [i-1] [j-1]. Kiểm tra xem phần tử thứ (i-1) của str1 và (j-1) của str2 có bằng nhau không, sau đó duyệt DP theo đường chéo.
Bây giờ, nếu phần tử thứ (i-1) của str1 và (j-1) phần tử thứ của str2 không bằng nhau. Giá trị của DP [i] [j] là (giá trị nhỏ nhất trong số DP [i-1] [j-1], DP [i] [j-1] vàDP [i-1] [j]) + 1.
Phương thức này có thể in một cách để chuyển đổi một chuỗi này sang chuỗi khác. Phương pháp in tất cả các cách hơi phức tạp là sử dụng cấu trúc dữ liệu nâng cao như vectơ chuỗi và chúng ta sẽ tìm hiểu về nó sau.
Chương trình minh họa hoạt động của phương pháp tiếp cận của chúng tôi,
Ví dụ
#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;
} Đầu ra
Way to convert one string into another string is Modify 'g' to 'p Insert 'q' Modify 'o' to 'a Modify 'e' to 'c