interleaving strings, hard

sherxon · May 21, 2018 · 65dffe4 · 65dffe4
1 parent 91528bd
commit 65dffe4
Show file tree

Hide file tree

Showing 2 changed files with 51 additions and 0 deletions.
diff --git a/src/problems/Hard.txt b/src/problems/Hard.txt
@@ -307,3 +307,15 @@ A.length * A[i].length <= 20000
 All words in A consist of lowercase letters only.
 All words in A have the same length and are anagrams of each other.
 The judging time limit has been increased for this question.
+
+18) Interleaving String
+Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
+
+Example 1:
+
+Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
+Output: true
+Example 2:
+
+Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
+Output: false
diff --git a/src/problems/hard/InterleavingStrings.java b/src/problems/hard/InterleavingStrings.java
@@ -0,0 +1,39 @@
+package problems.hard;
+
+/**
+ * Why Did you create this class? what does it do?
+ */
+public class InterleavingStrings {
+    public static void main(String[] args) {
+        System.out.println(new InterleavingStrings().isInterleave("aabcc", "dbbca", "aadbbbaccc"));
+    }
+
+    boolean found = false;
+
+    public boolean isInterleave(String s1, String s2, String s3) {
+        if (s1.length() == 0 && s2.length() == 0 && s3.length() == 0)
+            return true;
+        if (Math.min(s1.length(), s2.length()) == 0 && (s3.equals(s1) || s3.equals(s2)) && s3.length() > 0)
+            return true;
+        go(s1.toCharArray(), s2.toCharArray(), s3.toCharArray(), 0, 0, 0);
+        return found;
+    }
+
+    void go(char[] a, char[] b, char[] c, int i, int j, int k) {
+        if (found)
+            return;
+        if (k >= c.length) {
+            if (i > 0 && j > 0)
+                found = true;
+            return;
+        }
+
+        if (i < a.length && a[i] == c[k]) {
+            go(a, b, c, i + 1, j, k + 1);
+        }
+        if (j < b.length && b[j] == c[k]) {
+            go(a, b, c, i, j + 1, k + 1);
+        }
+
+    }
+}