資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學透過刪除字串A兩端字元並在任意位置重新插入字元，將其轉換為字串B
字串的變位詞是指包含與另一個字串完全相同的字元的字串，但字元順序可能與原始字串不同，因此我們稱這兩個字串互為變位詞。這裡我們給出了兩個互為變位詞的字串，第一個和第二個。我們的任務是最小化操作次數，以使第一個字串與第二個字串相同。
一個操作是指我們可以從第一個字串的開頭或結尾刪除一個字元，然後將其重新插入到任意位置。
示例
輸入
First: "hello", Second: "ohlle"
輸出
3
解釋
在這裡，我們執行最少的操作以使第一個字串與第二個字串相同：
從第一個字串中刪除最後一個字元並將其放在索引0處，“ohell”
再次，從更新後的第一個字串中刪除最後一個字元並將其放在索引2處，“ohlel”
再次，從更新後的第一個字串中刪除最後一個字元並將其放在索引3處，“ohlle”
輸入
First: "world", Second: "world"
輸出
0
解釋
因為這裡第一個字串和第二個字串彼此相等。
使用LCS概念的動態方法
我們將使用最長公共子序列 (LCS) 的概念來解決這個問題，這是一個非常流行的動態規劃問題。
示例
讓我們看看下面的程式碼，以便更好地理解上述方法。
#include <bits/stdc++.h>
using namespace std;
// Create a function to minimize the count of operations
int minimizeCountOfOperations(string First, string Second){
// Create an 2d matrix to maintain the longest continous length of first string that is part of the string second subsequence
int t[1001][1001];
// Variable maxlen store the maximum value of 2d matrix d
int maxlen = 0;
for (int i = 0; i <= First.size(); i++) {
for (int j = 0; j <= Second.size(); j++) {
t[i][j] = 0;
if (i && j) {
// if the sufix of first string is part of both second string upto j and also j-1
t[i][j] = t[i][j - 1];
// last charcter of both the string equal, then suffix of first string upto i-1 is part of second string upto j-1
if (First[i - 1] == Second[j - 1]) {
t[i][j] = max(t[i][j],1 + t[i - 1][j - 1]);
maxlen = max(maxlen, t[i][j]);
}
}
}
}
return First.size() - maxlen;
}
int main(){
string First = "hello";
string Second = "ohlle";
int minCount = minimizeCountOfOperations(First, Second);
cout << "Count of Minimum Operation needed to transform first string into second string is: " << minCount;
return 0;
}
輸出
Count of Minimum Operation needed to transform first string into second string is: 3
時間和空間複雜度
上述程式碼的時間複雜度為 O(N^2)。
上述程式碼的空間複雜度為 O(N^2)，因為我們使用二維矩陣來儲存結果。
這裡 N 是給定字串的大小。
使用陣列代替二維矩陣的上述方法的高效版本
這與上述方法相同，唯一的區別是這裡我們使用線性陣列而不是二維矩陣，這將為我們提供更好的空間複雜度。這將降低空間複雜度，因為我們將修剪不需要的結果並將其替換為新計算的值。
示例
讓我們看看下面的程式碼，以便更好地理解上述方法。
#include <bits/stdc++.h>
using namespace std;
// Create a function to minimize the count of operations
int minimizeCountOfOperations(string First, string Second){
// Create an array to maintain the longest continous length of first string that is part of the string second subsequence and assign it 0
int t[1001] = {0};
// Variable maxlen store the maximum value of 2d matrix d
int maxlen = 0;
for (int i = 1; i <= First.size(); i++) {
int previousVal = 0;
for (int j = 1; j <= Second.size(); j++) {
int store = t[j];
t[j] =t[j-1];
if(First[i - 1] == Second[j - 1])
t[j] = max(t[j], previousVal+1);
else
t[j] = max(t[j], 0);
previousVal = store;
maxlen = max(maxlen, t[j]);
}
}
return First.size() - maxlen;
}
int main(){
string First = "hello";
string Second = "ohlle";
int minCount = minimizeCountOfOperations(First, Second);
cout << "Count of Minimum Operation needed to transform first string into second string is: " << minCount;
return 0;
}
輸出
Count of Minimum Operation needed to transform first string into second string is: 3
時間和空間複雜度
上述程式碼的時間複雜度為 O(N^2)。
上述程式碼的空間複雜度為 O(N)，因為我們使用的是陣列。
這裡 N 是給定字串的大小。
結論
在本教程中，我們實現了一個 C++ 程式，透過刪除字元的兩端並在任意位置重新插入它們來將字串 A 轉換為字串 B。我們已經實現了兩種方法來解決這個問題。方法是使用 LCS 概念的具有二維矩陣的動態方法，以及使用陣列代替二維矩陣的第一種方法的高效版本。
65 次瀏覽
