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

  • 对于 i 从 1 到 n

    • 对于 j 从 1 到 m

      • 如果 s[i] = t[j]，那么

        • dp[i, j] := dp[i – 1, j – 1]

      • dp[i, j] := dp[i, j] + dp[i – 1, 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

更新于:09-6 月-2020

246 次浏览

开启你的 职业生涯

完成课程以获得认证

开始学习
广告