I like to read this solution as a small machine: keep the useful information, throw away the noise. For 115. Distinct Subsequences, the solution in this repository is mainly a dynamic programming solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: dynamic programming, prefix sums, bit manipulation, backtracking.
The notes already sitting in the source point us in the right direction:
- backtracking
- TLE
- 52 / 63 test cases passed.
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are backtrack, numDistinct.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//backtracking
02//TLE
03//52 / 63 test cases passed.
04class Solution {
05public:
06 string s, t;
07 int ans;
08
09 void backtrack(int start, string& cur){
10 if(cur.size() == t.size()){
11 //here cur == t must hold
12 ++ans;
13 }else if(cur.size() < t.size() &&
14 cur.size() + s.size() - start >= t.size()){
15 //use s[start]
16 if(s[start] == t[cur.size()]){
17 cur.push_back(s[start]);
18 backtrack(start+1, cur);
19 cur.pop_back();
20 }
21
22 //not use s[start]
23 backtrack(start+1, cur);
24 }
25 }
26
27 int numDistinct(string s, string t) {
28 this->s = s;
29 this->t = t;
30 ans = 0;
31
32 string cur;
33 backtrack(0, cur);
34
35 return ans;
36 }
37};
38
39//backtracking + memorization
40//Runtime: 476 ms, faster than 8.83% of C++ online submissions for Distinct Subsequences.
41//Memory Usage: 113.1 MB, less than 5.01% of C++ online submissions for Distinct Subsequences.
42struct pair_hash {
43 template <class T1, class T2>
44 std::size_t operator () (const std::pair<T1,T2> &p) const {
45 auto h1 = std::hash<T1>{}(p.first);
46 auto h2 = std::hash<T2>{}(p.second);
47
48 // Mainly for demonstration purposes, i.e. works but is overly simple
49 // In the real world, use sth. like boost.hash_combine
50 return h1 ^ h2;
51 }
52};
53
54class Solution {
55public:
56 string s, t;
57
58 unordered_map<pair<int, string>, int, pair_hash> memo;
59
60 int backtrack(int start, string& cur){
61 if(memo.find({start, cur}) != memo.end()){
62 return memo[{start, cur}];
63 }else if(cur.size() == t.size()){
64 //here cur == t must hold
65 return memo[{start, cur}] = 1;
66 }else if(cur.size() < t.size() &&
67 cur.size() + s.size() - start >= t.size()){
68 int ret = 0;
69
70 //use s[start]
71 if(s[start] == t[cur.size()]){
72 cur.push_back(s[start]);
73 ret += backtrack(start+1, cur);
74 cur.pop_back();
75 }
76
77 //not use s[start]
78 ret += backtrack(start+1, cur);
79
80 return memo[{start, cur}] = ret;
81 }
82
83 return 0;
84 }
85
86 int numDistinct(string s, string t) {
87 this->s = s;
88 this->t = t;
89
90 string cur;
91 return backtrack(0, cur);
92 }
93};
94
95//top-down DP
96//actually we don't need to keep the string "cur", because it must be a prefix of "t", so we can simply use the index "ti"
97//Runtime: 16 ms, faster than 47.28% of C++ online submissions for Distinct Subsequences.
98//Memory Usage: 11.9 MB, less than 5.01% of C++ online submissions for Distinct Subsequences.
99class Solution {
100public:
101 string s, t;
102 vector<vector<int>> dp;
103
104 int backtrack(int si, int ti){
105 if(dp[si][ti] != -1){
106 return dp[si][ti];
107 }else if(ti == t.size()){
108 return dp[si][ti] = 1;
109 }else if(ti < t.size() &&
110 ti + s.size() - si >= t.size()){
111 int ret = 0;
112
113 //use s[si]
114 if(s[si] == t[ti]){
115 //ti+1: because t[ti] is matched
116 ret += backtrack(si+1, ti+1);
117 }
118
119 //not use s[si]
120 ret += backtrack(si+1, ti);
121
122 return dp[si][ti] = ret;
123 }
124
125 return dp[si][ti] = 0;
126 }
127
128 int numDistinct(string s, string t) {
129 this->s = s;
130 this->t = t;
131
132 dp = vector<vector<int>>(s.size()+1, vector<int>(t.size()+1, -1));
133
134 return backtrack(0, 0);
135 }
136};
137
138//bottom-up DP
139//https://leetcode.com/problems/distinct-subsequences/discuss/37327/Easy-to-understand-DP-in-Java
140//https://leetcode.com/problems/distinct-subsequences/discuss/37327/Easy-to-understand-DP-in-Java/35364
141//Runtime: 12 ms, faster than 66.64% of C++ online submissions for Distinct Subsequences.
142//Memory Usage: 12.5 MB, less than 5.01% of C++ online submissions for Distinct Subsequences.
143class Solution {
144public:
145 int numDistinct(string s, string t) {
146 int ssz = s.size(), tsz = t.size();
147
148 //need to use long long?!
149 vector<vector<long long>> dp(tsz+1, vector<long long>(ssz+1, 0));
150
151 //first row: empty t
152 //dp[0][...] = 1
153 for(int j = 0; j <= ssz; ++j){
154 dp[0][j] = 1;
155 }
156
157 //first col: non-empty t, empty s
158 //dp[1:][0] = 0
159
160 for(int i = 1; i <= tsz; ++i){
161 //compare t[...i-1] with s's substrings
162 //think t[...i-1] as fixed and keep lengthen s
163 for(int j = 1; j <= ssz; ++j){
164 //i, j: length of compared substrings
165 if(s[j-1] == t[i-1]){ //note: it's NOT s[j] == t[i] here!!
166 /*
167 when we don't match s[j-1] and t[i-1],
168 we have the same way as matching s[0...j-2] and t[i-1],
169 which is dp[i][j-1]
170
171 when we match s[j-1] and t[i-1],
172 we have the same way as matching s[0...j-2] and t[0...i-2],
173 which is dp[i-1][j-1]
174 */
175 dp[i][j] = dp[i][j-1] + dp[i-1][j-1];
176 }else{
177 /*
178 if s[j-1] != t[i-1], that means s[j-1] has no effect,
179 so the result is same as that when s[j-1] doesn't exist
180 */
181 dp[i][j] = dp[i][j-1];
182 }
183 }
184 }
185
186 return dp[tsz][ssz];
187 }
188};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.