C ++中的不同子序列

假设我们有字符串S和T。我们必须计算等于T的S的不同序列数。

我们知道一个字符串的子序列是一个新字符串，它是通过删除一些字符（可以是无字符）而不会干扰其余字符的相对位置而从原始字符串形成的。（例如，“ ACE”是“ ABCDE”的子序列，而“ AEC”则不是）。

如果输入字符串是“ baalllloonnn”和“ balloon”，那么将有36种不同的选择方式。

为了解决这个问题，我们将遵循以下步骤-

• n：= s的大小，m：= t的大小。通过在空格之前连接s和t来更新它们

• 制作一个大小为（n + 1）x（m + 1）的矩阵

• 设置dp [0，0]：= 1，然后为所有行的第0列设置1，放入1

• 对于我在1到n范围内

• 如果s [i] = t [j]，则

• dp [i，j]：= dp [i，j] + dp [i – 1，j]

• dp [i，j]：= dp [i – 1，j – 1]

• 对于1到m范围内的j

• 返回dp [n，m]

示例

让我们看下面的实现以更好地理解-

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
   public:
   int numDistinct(string s, string t) {
      int n = s.size();
      int m = t.size();
      s = " " + s;
      t = " " + t;
      vector < vector <lli>> dp(n + 1, vector <lli> (m + 1));
      dp[0][0] = 1;
      for(int i = 1; i<= n; i++)dp[i][0] = 1;
      for(int i = 1; i <= n; i++){
         for(int j = 1; j <= m; j++){
            if(s[i] == t[j]) dp[i][j] = dp[i - 1][j - 1];
            dp[i][j]+= dp[i - 1][j];
         }
      }
      return dp[n][m];
   }
};
main(){
   Solution ob;
   cout << (ob.numDistinct("baalllloonnn", "balloon"));
}

输入值

"baalllloonnn"
"balloon"

输出结果

36