假设我们有字符串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