資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
廣告