資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究給定字串 X 在字串 Y 和 Z 之間的子序列計數
子序列是從另一個字串中刪除一些（可能沒有或全部）字元得到的字串，這些字元可能不是連續的。給定一個字串，我們必須找到大於等於給定字串 Y 且小於等於另一個給定字串 Z 的子序列的數量。我們將使用動態規劃來解決這個問題，因為暴力方法將花費指數時間。
暴力方法
暴力方法是找到給定字串 X 的所有子序列，然後檢查它們是否在給定的範圍內。如果當前子序列在給定的範圍內，那麼我們將增加計數。
示例
#include <bits/stdc++.h>
using namespace std;
// global varaibles
string x, y, z;
int len_x, len_y, len_z;
// recursive function
int rec(string& cur, int i){
// defining the base cases
if(i == len_x){
if(cur <=z && cur >= y){
return 1;
} else {
return 0;
}
}
int ans = rec(cur, i + 1);
cur.push_back(x[i]);
ans += rec(cur, i + 1);
cur.pop_back();
return ans;
}
// function to get the number of subsequences less than Z and greater than Y
int getCount(string X, string Y, string Z){
string cur = ""; // initializing empty string
// getting the length of the given strings
len_x = X.size();
len_y = Y.size();
len_z = Z.size();
// calling to the recursive function to get the result
return rec(cur, 0);
}
int main(){
// given strings
x = "abc";
y = "a";
z = "bc";
// edge case, if the given string y is greater than z
// return zero
if(y > z){
cout<<"The number of subsequences of given string X in between strings Y and Z are: "<<0<<endl;
} else {
// calling the function
cout<<"The number of subsequences of given string X in between strings Y and Z are: "<<getCount(x,y,z) <<endl;
}
return 0;
}
輸出
The number of subsequences of given string X in between strings Y and Z are: 6
時間和空間複雜度
以上程式碼的時間複雜度為 O((2^N) * N)，其中 N 是給定字串的大小。
以上程式碼的空間複雜度為 O(N)，因為我們使用字串來儲存當前字串。
動態規劃方法
我們將在每個索引處做出選擇，在第一個選擇中，我們將跳過當前索引值並移動到下一個值，在第二個選擇中，我們將檢查透過將當前字元新增到字串中是否在範圍內。
如果透過將當前元素新增到字串中，我們將得到範圍內的結果，那麼我們將新增到答案中。此外，如果我們已經訪問過此狀態，那麼我們將返回已儲存的答案。
示例
#include <bits/stdc++.h>
using namespace std;
// array to store the state results
int memo[105][105][2][2];
// global variables
string x, y, z;
int len_x, len_y, len_z;
// recursive function
int rec(int i, int j, bool var1, bool var2){
// defining the base cases
if(i == len_x){
// if subsequence is empty then return 0
if (j == 0){
return 0;
}
if(var1 == false || j >= len_y){
return 1;
} else {
return 0;
}
}
// if the memo array contains this item then return it
if(memo[i][j][var1][var2] != -1){
return memo[i][j][var1][var2];
}
// skip the current index
int res = rec(i + 1, j, var1, var2);
// variable to mark the position of current index
int canAdded = 0;
if(var1 == false) {
canAdded = 1;
} else if ((j >= len_y) || (x[i] >= y[j])) {
canAdded = 1;
var1 &= ((j < len_y) && x[i] == y[j]);
}
if (var2 == false){
canAdded ++;
} else if((j < len_z) && x[i] <= z[j]){
canAdded++;
var2 &= (x[i] == z[j]);
}
if (canAdded == 2){
// increase both i and j by 1
res += rec(i + 1, j + 1, var1, var2);
}
// store the answer in memo array
memo[i][j][var1][var2] = res;
return res;
}
// function to get the number of subsequences less than Z and greater than Y
int getCount(string X, string Y, string Z){
// initialize the memo function
memset(memo, -1, sizeof(memo));
// getting the lenght of the given strings
len_x = X.size();
len_y = Y.size();
len_z = Z.size();
// calling to the recursive function to get the result
return rec(0, 0, 1, 1);
}
int main(){
// given strings
x = "abc";
y = "a";
z = "bc";
// edge case, if the given string y is greater than z
// return zero
if(y > z){
cout<<"The number of subsequences of given string X in between strings Y and Z are: "<<0<<endl;
} else {
// calling the function
cout<<"The number of subsequences of given string X in between strings Y and Z are: "<<getCount(x,y,z) <<endl;
}
return 0;
}
輸出
The number of subsequences of given string X in between strings Y and Z are: 6
時間和空間複雜度
以上程式碼的時間複雜度為 O(N*N)，其中 N 是給定字串的大小。
以上程式碼的空間複雜度為 O(N*N)，因為我們使用陣列來儲存結果或狀態。
結論
在本教程中，我們實現了一個程式來查詢位於給定字串 Y 和 Z 之間的字串 X 的子序列的數量。我們已經看到了效率低下的簡單暴力方法，然後我們實現了高效的動態規劃程式碼，其時間複雜度為 O(N*N)，空間複雜度相同。
更新於: 2023年8月24日
103 次瀏覽
廣告