C++ 在字符串Y和Z之间给定字符串X的子序列计数

子序列是可以通过从给定字符串中删除某些字符（可能是零个、一个或全部）而获得的字符串，这些字符可能不连续。我们给定一个字符串，并要找到大于等于给定字符串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)，因为我们使用一个数组来存储结果或状态。

结论

在本教程中，我们实现了一个程序，用来查找字符串X中位于给定字符串Y和Z之间的子序列数量。我们先介绍了简单的蛮力方法，然后实现了时间复杂度为O(N*N)和相同空间复杂度的有效的动态规划代码。