package com.fishercoder.solutions;

/**
 * Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
 * <p>
 * For example,
 * Given:
 * s1 = "aabcc",
 * s2 = "dbbca",
 * <p>
 * When s3 = "aadbbcbcac", return true.
 * When s3 = "aadbbbaccc", return false.
 */
public class _97 {
    public boolean isInterleave(String s1, String s2, String s3) {
        // write your code here
        int m = s1.length();
        int n = s2.length();
        if (m + n != s3.length()) {
            return false;
        }

        boolean[][] dp = new boolean[m + 1][n + 1];

        dp[0][0] = true;

        for (int i = 0; i < m; i++) {
            if (s1.charAt(i) == s3.charAt(i)) {
                dp[i + 1][0] = true;
            } else {
                //if one char fails, that means it breaks, the rest of the chars won't matter any more.
                //Mian and I found one missing test case on Lintcode: ["b", "aabccc", "aabbbcb"]
                //if we don't break, here, Lintcode could still accept this code, but Leetcode fails it.
                break;
            }
        }

        for (int j = 0; j < n; j++) {
            if (s2.charAt(j) == s3.charAt(j)) {
                dp[0][j + 1] = true;
            } else {
                break;
            }
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                int k = i + j - 1;
                dp[i][j] = (s1.charAt(i - 1) == s3.charAt(k) && dp[i - 1][j])
                        || (s2.charAt(j - 1) == s3.charAt(k) && dp[i][j - 1]);
            }
        }

        return dp[m][n];
    }
}

@@ -33,16 +33,46 @@
 s;%0A%0A/**%0A
+ * 97. Interleaving String%0A *%0A
  * Given
@@ -144,23 +144,16 @@
 and s2.%0A
- * %3Cp%3E%0A
  * For e
@@ -208,15 +208,8 @@
 a%22,%0A
- * %3Cp%3E%0A
  * W
@@ -308,16 +308,50 @@
 s _97 %7B%0A
+  public static class Solution1 %7B%0A
     publ
@@ -413,42 +413,8 @@
 ) %7B%0A
-        // write your code here%0A  
     
@@ -432,26 +432,24 @@
 1.length();%0A
-  
       int n 
@@ -465,26 +465,24 @@
 th();%0A      
-  
 if (m + n !=
@@ -501,28 +501,24 @@
 ) %7B%0A        
-   
- 
 return false
@@ -521,31 +521,27 @@
 alse;%0A      
-  
 %7D%0A%0A
-  
       boolea
@@ -581,26 +581,24 @@
  1%5D;%0A%0A      
-  
 dp%5B0%5D%5B0%5D = t
@@ -603,18 +603,16 @@
  true;%0A%0A
-  
       fo
@@ -643,28 +643,24 @@
 ) %7B%0A        
- 
-   
 if (s1.charA
@@ -689,30 +689,24 @@
 %7B%0A          
-      
 dp%5Bi + 1%5D%5B0%5D
@@ -714,36 +714,32 @@
 = true;%0A        
- 
-   
 %7D else %7B%0A       
@@ -723,38 +723,32 @@
        %7D else %7B%0A
-      
           //if o
@@ -839,22 +839,16 @@
         
- 
-     
 //Mian a
@@ -926,30 +926,24 @@
 %5D%0A          
-     
- 
 //if we don'
@@ -1029,33 +1029,23 @@
         
-      
 break;%0A
-    
         
@@ -1044,39 +1044,35 @@
         %7D%0A      
-  
 %7D%0A%0A
-  
       for (int j
@@ -1095,28 +1095,24 @@
 ) %7B%0A        
- 
-   
 if (s2.charA
@@ -1145,22 +1145,16 @@
         
-  
-    
 dp%5B0%5D%5Bj 
@@ -1170,28 +1170,24 @@
 ue;%0A        
-    
 %7D else %7B%0A   
@@ -1189,30 +1189,24 @@
 %7B%0A          
-  
-    
 break;%0A     
@@ -1204,32 +1204,26 @@
 ak;%0A        
-    %7D%0A  
+%7D%0A
       %7D%0A%0A   
@@ -1221,26 +1221,24 @@
    %7D%0A%0A      
-  
 for (int i =
@@ -1264,20 +1264,16 @@
         
-   
- 
 for (int
@@ -1305,22 +1305,16 @@
         
-    
-  
 int k = 
@@ -1324,22 +1324,16 @@
  j - 1;%0A
-      
         
@@ -1410,26 +1410,16 @@
         
-  
-        
 %7C%7C (s2.c
@@ -1473,28 +1473,24 @@
         
-    
 %7D%0A      
   %7D%0A%0A   
@@ -1477,31 +1477,27 @@
     %7D%0A      
-  
 %7D%0A%0A
-  
       return
@@ -1513,10 +1513,14 @@
 ;%0A    %7D%0A
+  %7D%0A
 %7D%0A

refactor 97