diff options
Diffstat (limited to 'other/interleaving_string.cpp')
-rw-r--r-- | other/interleaving_string.cpp | 39 |
1 files changed, 39 insertions, 0 deletions
diff --git a/other/interleaving_string.cpp b/other/interleaving_string.cpp new file mode 100644 index 0000000..ed2a5b9 --- /dev/null +++ b/other/interleaving_string.cpp @@ -0,0 +1,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"; +} |