leetcode

0 class Solution {

1 short int dp[101][101];

2 bool rec(const string &s1, const string &s2, const string &s3, int i = 0, int j = 0, int k = 0) {

3 if (k == s3.size()) return true;

4 if (dp[i][j] != -1) return dp[i][j];

5

6 if (i != s1.size() && s1[i] == s3[k] && rec(s1, s2, s3, i + 1, j, k + 1)) return dp[i][j] = true;

7

8 if (j != s2.size() && s2[j] == s3[k] && rec(s1, s2, s3, i, j + 1, k + 1)) return dp[i][j] = true;

9

10 return dp[i][j] = false;

11 }

12

13 public:

14 Solution() { memset(dp, 0xFF, sizeof(dp)); }

15 bool isInterleave(const string &s1, const string &s2, const string &s3) {

16 if (s1.size() + s2.size() != s3.size()) return false;

17 return rec(s1, s2, s3);

18 }

19 };