打印所有可能的方法以在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