aboutsummaryrefslogtreecommitdiff
path: root/interleaving_string.cpp
blob: ed2a5b91dd6c84f7a8813fb3c51a87aeea5a1a3b (plain)
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";
}