-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDistinct_Subsequences.cpp
More file actions
24 lines (21 loc) · 643 Bytes
/
Copy pathDistinct_Subsequences.cpp
File metadata and controls
24 lines (21 loc) · 643 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
int numDistinct(string S, string T) {
int m = S.size();
int n = T.size();
vector<vector<int>> tbl(m+1, vector<int>(n+1, 0));
for(int i = 0; i <= m; i++){
for(int j = 0; j <= n; j++){
if(j == 0) tbl[i][j] = 1;
if(i > 0 && j > 0){
if(S[i-1] == T[j-1]){
tbl[i][j] = tbl[i-1][j] + tbl[i-1][j-1];
}else{
tbl[i][j] = tbl[i-1][j];
}
}
}
}
return tbl[m][n];
}
};