aboutsummaryrefslogtreecommitdiff
path: root/other/interleaving_string.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/interleaving_string.cpp')
-rw-r--r--other/interleaving_string.cpp39
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";
+}