ในปัญหานี้ เราได้รับสองสตริง 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] ตรวจสอบว่าองค์ประกอบ (i-1)th ขององค์ประกอบ str1 และ (j-1)th ของ str2 เท่ากันหรือไม่ จากนั้นข้าม DP ในแนวทแยง
ทีนี้ ถ้าองค์ประกอบ (i-1)th ขององค์ประกอบ str1 และ (j-1)th ของ str2 ไม่เท่ากัน ค่าของ DP[i][j] คือ (ค่าต่ำสุดจาก DP[i-1][j-1] , DP[i][j-1] andDP[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
