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
|
#include "leetcode.h"
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
memset(t, -1, sizeof(t));
m = s1.size();
n = s2.size();
N = s3.size();
if (m + n != N)
return false;
return helper(s1, s2, s3, 0, 0);
}
private:
int m, n, N;
int t[101][101];
bool helper(string s1, string s2, string s3, int i, int j) {
if (i >= m && j >= n && i + j >= N)
return true;
if (i + j >= N)
return false;
if (t[i][j] != -1)
return t[i][j];
return t[i][j] = ((s1[i] == s3[i + j] && helper(s1, s2, s3, i + 1, j)) ||
(s2[j] == s3[i + j] && helper(s1, s2, s3, i, j + 1)));
}
};
int main() {
Solution obj;
string s1 = "aabcc";
string s2 = "dbbca";
string s3 = "aadbbcbcac";
if (obj.isInterleave(s1, s2, s3))
cout << "true";
else
cout << "false";
}
|