数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用 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<<"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
更新于： 2021年1月25日
196 次查看
广告