Let's make this one less mysterious. For 97. Interleaving String, the solution in this repository is mainly a DFS + memoization solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. 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: DFS + memoization, dynamic programming.
The notes already sitting in the source point us in the right direction:
- recursion
- TLE
- 99 / 101 test cases passed.
- time: O(2^(m+n)), space: O(m+n)
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 dfs, isInterleave.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- Substring checks are convenient but not free, so they are part of the real complexity story.
- 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(2^(m+n)), space: O(m+n)
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//recursion
02//TLE
03//99 / 101 test cases passed.
04//time: O(2^(m+n)), space: O(m+n)
05class Solution {
06public:
07 bool dfs(string& s1, string& s2, string& s3, int i, int j){
08 // cout << i << ", " << j << endl;
09 if(i+j == s1.size() + s2.size()){
10 return true;
11 }
12
13 if(i < s1.size() && s1[i] == s3[i+j]){
14 if(dfs(s1, s2, s3, i+1, j)) return true;
15 }
16 if(j < s2.size() && s2[j] == s3[i+j]){
17 if(dfs(s1, s2, s3, i, j+1)) return true;
18 }
19
20 return false;
21 };
22
23 bool isInterleave(string s1, string s2, string s3) {
24 if(s1.size() + s2.size() != s3.size()) return false;
25 return dfs(s1, s2, s3, 0, 0);
26 }
27};
28
29//recursion + memorization
30//Runtime: 8 ms, faster than 52.84% of C++ online submissions for Interleaving String.
31//Memory Usage: 6.8 MB, less than 39.08% of C++ online submissions for Interleaving String.
32class Solution {
33public:
34 vector<vector<int>> memo;
35
36 bool dfs(string& s1, string& s2, string& s3, int i, int j){
37 // cout << i << ", " << j << endl;
38 if(i+j == s1.size() + s2.size()){
39 return true;
40 }
41
42 if(memo[i][j] != -1){
43 return memo[i][j];
44 }
45
46 if(i < s1.size() && s1[i] == s3[i+j]){
47 if(dfs(s1, s2, s3, i+1, j)) return memo[i][j] = true;
48 }
49 if(j < s2.size() && s2[j] == s3[i+j]){
50 if(dfs(s1, s2, s3, i, j+1)) return memo[i][j] = true;
51 }
52
53 return memo[i][j] = false;
54 };
55
56 bool isInterleave(string s1, string s2, string s3) {
57 if(s1.size() + s2.size() != s3.size()) return false;
58 int m = s1.size(), n = s2.size();
59 memo = vector<vector<int>>(m+1, vector<int>(n+1, -1));
60 return dfs(s1, s2, s3, 0, 0);
61 }
62};
63
64//recursion + memorization, early stopping
65//Runtime: 0 ms, faster than 100.00% of C++ online submissions for Interleaving String.
66//Memory Usage: 7 MB, less than 33.14% of C++ online submissions for Interleaving String.
67//time: O(m*n), space: O(m*n)
68class Solution {
69public:
70 vector<vector<int>> memo;
71
72 bool dfs(string& s1, string& s2, string& s3, int i, int j){
73 // cout << i << ", " << j << endl;
74 if(i+j == s1.size() + s2.size()){
75 return true;
76 }else if(i == s1.size()){
77 return s2.substr(j) == s3.substr(i+j);
78 }else if(j == s2.size()){
79 return s1.substr(i) == s3.substr(i+j);
80 }
81
82 if(memo[i][j] != -1){
83 return memo[i][j];
84 }
85
86 if(i < s1.size() && s1[i] == s3[i+j]){
87 if(dfs(s1, s2, s3, i+1, j)) return memo[i][j] = true;
88 }
89 if(j < s2.size() && s2[j] == s3[i+j]){
90 if(dfs(s1, s2, s3, i, j+1)) return memo[i][j] = true;
91 }
92
93 return memo[i][j] = false;
94 };
95
96 bool isInterleave(string s1, string s2, string s3) {
97 if(s1.size() + s2.size() != s3.size()) return false;
98 int m = s1.size(), n = s2.size();
99 memo = vector<vector<int>>(m, vector<int>(n, -1));
100 return dfs(s1, s2, s3, 0, 0);
101 }
102};
103
104//DP
105//Runtime: 8 ms, faster than 52.84% of C++ online submissions for Interleaving String.
106//Memory Usage: 6.7 MB, less than 49.81% of C++ online submissions for Interleaving String.
107class Solution {
108public:
109 bool isInterleave(string s1, string s2, string s3) {
110 if(s1.size() + s2.size() != s3.size()) return false;
111 int m = s1.size(), n = s2.size();
112 vector<vector<bool>> dp(m+1, vector<bool>(n+1, false));
113
114 for(int i = m; i >= 0; --i){
115 for(int j = n; j >= 0; --j){
116 if(i == m && j == n){
117 dp[i][j] = true;
118 }else{
119 if(s1[i] == s3[i+j] && dp[i+1][j]){
120 dp[i][j] = true;
121 continue;
122 }
123 if(s2[j] == s3[i+j] && dp[i][j+1]){
124 dp[i][j] = true;
125 continue;
126 }
127 dp[i][j] = false;
128 }
129 }
130 }
131
132 return dp[0][0];
133 }
134};
135
136//DP, bottom up
137//Runtime: 8 ms, faster than 52.84% of C++ online submissions for Interleaving String.
138//Memory Usage: 6.5 MB, less than 68.01% of C++ online submissions for Interleaving String.
139//time: O(m*n), space: O(m*n)
140class Solution {
141public:
142 bool isInterleave(string s1, string s2, string s3) {
143 if(s1.size() + s2.size() != s3.size()) return false;
144 int m = s1.size(), n = s2.size();
145 /*
146 dp[i][j]: seen i char in s1, j char in s2,
147 so we are currently looking at s1[i-1] and s2[j-1]
148 */
149 vector<vector<bool>> dp(m+1, vector<bool>(n+1, false));
150
151 for(int i = 0; i <= m; ++i){
152 for(int j = 0; j <= n; ++j){
153 if(i == 0 && j == 0){
154 dp[i][j] = true;
155 }else if(i == 0){
156 /*
157 after dp[0][j], we have seen
158 0 chars from s1 and j chars from s2,
159 so it means we are looking at s2[j-1]
160 */
161 dp[i][j] = (s2[j-1] == s3[i+j-1]) && dp[i][j-1];
162 }else if(j == 0){
163 dp[i][j] = (s1[i-1] == s3[i+j-1]) && dp[i-1][j];
164 }else{
165 dp[i][j] = (s1[i-1] == s3[i+j-1] && dp[i-1][j])
166 || (s2[j-1] == s3[i+j-1] && dp[i][j-1]);
167 }
168 }
169 }
170
171 return dp[m][n];
172 }
173};
174
175//O(N) DP
176//Runtime: 4 ms, faster than 84.58% of C++ online submissions for Interleaving String.
177//Memory Usage: 6.3 MB, less than 83.14% of C++ online submissions for Interleaving String.
178class Solution {
179public:
180 bool isInterleave(string s1, string s2, string s3) {
181 if(s1.size() + s2.size() != s3.size()) return false;
182 int m = s1.size(), n = s2.size();
183 vector<vector<bool>> dp(2, vector<bool>(n+1, false));
184
185 for(int i = m; i >= 0; --i){
186 for(int j = n; j >= 0; --j){
187 if(i == m && j == n){
188 dp[i&1][j] = true;
189 }else{
190 if(s1[i] == s3[i+j] && dp[(i+1)&1][j]){
191 dp[i&1][j] = true;
192 continue;
193 }
194 if(s2[j] == s3[i+j] && dp[i&1][j+1]){
195 dp[i&1][j] = true;
196 continue;
197 }
198 dp[i&1][j] = false;
199 }
200 }
201 }
202
203 return dp[0][0];
204 }
205};
206
207//1-D DP
208//Runtime: 4 ms, faster than 84.58% of C++ online submissions for Interleaving String.
209//Memory Usage: 6.1 MB, less than 94.44% of C++ online submissions for Interleaving String.
210//time: O(m*n), space: O(n)
211class Solution {
212public:
213 bool isInterleave(string s1, string s2, string s3) {
214 if(s1.size() + s2.size() != s3.size()) return false;
215 int m = s1.size(), n = s2.size();
216
217 /*
218 dp[i][j] depends on dp[i-1][j] and dp[i][j-1]
219 for dp[i-1][j], since we visit i from 0 to m, so it's safe
220 for dp[i][j-1], since we visit j from 0 to n, so it's safe
221 */
222 vector<bool> dp(n+1, false);
223
224 for(int i = 0; i <= m; ++i){
225 for(int j = 0; j <= n; ++j){
226 if(i == 0 && j == 0){
227 dp[j] = true;
228 }else if(i == 0){
229 dp[j] = (s2[j-1] == s3[i+j-1]) && dp[j-1];
230 }else if(j == 0){
231 dp[j] = (s1[i-1] == s3[i+j-1]) && dp[j];
232 }else{
233 dp[j] = (s1[i-1] == s3[i+j-1] && dp[j])
234 || (s2[j-1] == s3[i+j-1] && dp[j-1]);
235 }
236 }
237 }
238
239 return dp[n];
240 }
241};Cost
Complexity
Time
O(2^(m+n)), space: O(m+n)
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.