打印所有可能的方法以在C ++中将一个字符串转换为另一字符串
在这个问题中，我们给了两个字符串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<<"将一个字符串转换为另一字符串的方法是 ";
findWays(str1, str2);
return 0;
}输出结果将一个字符串转换为另一字符串的方法是 Modify 'g' to 'p Insert 'q' Modify 'o' to 'a Modify 'e' to 'c
热门推荐
10 八一幼儿祝福语大全简短
11 公司乔迁食堂祝福语简短
12 婚礼结束聚餐祝福语简短
13 儿媳买车妈妈祝福语简短
14 毕业送礼老师祝福语简短
15 同事辞职正常祝福语简短
16 恭贺新婚文案祝福语简短
17 金店立秋祝福语简短英文
18 婆婆高寿祝福语大全简短