#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"; }