-
Notifications
You must be signed in to change notification settings - Fork 3
/
distinct-subsequences.cpp
92 lines (89 loc) · 2.67 KB
/
distinct-subsequences.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// 此题用三种方式解决, 重点是如何用滚动数组优化空间
// Time : O(N2), Memory : O(N2)
int numDistinct1(string &S, string &T) {
// write your code here
int n = S.length();
int m = T.length();
if(n == 0 || m == 0){
return 0;
}
vector<vector<int>> f(n+1, vector<int>(m+1, 0));
for(int i = 0; i <= n; i++){
f[i][0] = 1;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
f[i][j] = f[i-1][j];
if(S.at(i-1) == T.at(j-1)){
f[i][j] += f[i-1][j-1];
}
}
}
return f[n][m];
}
// V2 : 滚动数组优化Memory 到O(M)
int numDistinct(string &S, string &T) {
// write your code here
int n = S.length();
int m = T.length();
if(n == 0 || m == 0){
return 0;
}
vector<vector<int>> f(2, vector<int>(m+1, 0));
//f[0][0] = 1;
for(int i = 0; i <= n; i++){ // 注意 被优化的i必须在外层循环!!!
for(int j = 0; j <= m; j++){
if(j == 0){
f[i%2][0] = 1;
}
else if(i == 0){
f[i%2][j] = 0;
}
else{
f[i%2][j] = f[(i-1)%2][j];
if(S.at(i-1) == T.at(j-1)){
f[i%2][j] += f[(i-1)%2][j-1];
}
}
}
}
return f[n%2][m];
}
// V3 : 滚动数组优化Memory 到O(N)
int numDistinct3(string &S, string &T) {
// write your code here
int n = S.length();
int m = T.length();
if(n == 0 || m == 0){
return 0;
}
vector<vector<int>> f(n+1, vector<int>(2, 0));
for(int j = 0; j <= m; j++){ // 注意 被优化的j必须在外层循环!!!
for(int i = 0; i <= n; i++){
if(j == 0){
f[i][0]= 1;
}
else if(i == 0){
f[i][j%2] = 0;
}
else{
f[i][j%2] = f[i-1][j%2];
if(S.at(i-1) == T.at(j-1)){
f[i][j%2] += f[i-1][(j-1)%2];
}
}
//cout<<i<<","<<j<<"("<<j%2<<")"<<" : "<<f[i][j%2]<<endl;
}
}
return f[n][m%2];
}
int main(void){
string S = "ddd";
string T = "dd";
cout<<numDistinct(S, T)<<endl;
return 0;
}