数据结构
网络
关系型数据库管理系统
操作系统
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 次浏览
广告