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