package com.fishercoder.solutions;

/**
 * 97. Interleaving String
 *
 * Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
 * For example,
 * Given:
 * s1 = "aabcc",
 * s2 = "dbbca",
 * When s3 = "aadbbcbcac", return true.
 * When s3 = "aadbbbaccc", return false.
 */
public class _97 {
  public static class Solution1 {
    public boolean isInterleave(String s1, String s2, String s3) {
      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,268 +33,8 @@
 s;%0A%0A
-/**%0A * 97. Interleaving String%0A *%0A * Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.%0A * For example,%0A * Given:%0A * s1 = %22aabcc%22,%0A * s2 = %22dbbca%22,%0A * When s3 = %22aadbbcbcac%22, return true.%0A * When s3 = %22aadbbbaccc%22, return false.%0A */%0A
 publ
@@ -48,16 +48,18 @@
 s _97 %7B%0A
+  
   public
@@ -84,24 +84,28 @@
 tion1 %7B%0A    
+ 
+   
 public boole
@@ -151,24 +151,30 @@
 tring s3) %7B%0A
+      
       int m 
@@ -190,24 +190,30 @@
 th();%0A      
+ 
+     
 int n = s2.l
@@ -223,24 +223,30 @@
 th();%0A      
+  
+    
 if (m + n !=
@@ -257,24 +257,32 @@
 length()) %7B%0A
+        
         retu
@@ -293,27 +293,39 @@
 alse;%0A      
+    
+  
 %7D%0A%0A
+      
       boolea
@@ -363,16 +363,22 @@
  + 1%5D;%0A%0A
+      
       dp
@@ -391,32 +391,38 @@
  = true;%0A%0A      
+   
+   
 for (int i = 0; 
@@ -439,24 +439,32 @@
 ) %7B%0A        
+     
+   
 if (s1.charA
@@ -493,24 +493,34 @@
 %7B%0A          
+     
+     
 dp%5Bi + 1%5D%5B0%5D
@@ -528,32 +528,40 @@
 = true;%0A        
+       
+ 
 %7D else %7B%0A       
@@ -545,32 +545,42 @@
        %7D else %7B%0A
+          
           //if o
@@ -661,16 +661,26 @@
 y more.%0A
+          
         
@@ -762,16 +762,26 @@
 bbbcb%22%5D%0A
+          
         
@@ -871,16 +871,26 @@
 ils it.%0A
+          
         
@@ -902,35 +902,55 @@
 ak;%0A        
+  
-%7D%0A
+      %7D%0A     
       
+ 
 %7D%0A%0A
+      
       for (i
@@ -977,24 +977,32 @@
 ) %7B%0A        
+  
+      
 if (s2.charA
@@ -1031,24 +1031,34 @@
 %7B%0A          
+  
+        
 dp%5B0%5D%5Bj + 1%5D
@@ -1058,32 +1058,40 @@
 %5Bj + 1%5D = true;%0A
+        
         %7D else %7B
@@ -1101,31 +1101,48 @@
         
-break;%0A
+          break;%0A       
         
 %7D%0A      
@@ -1125,34 +1125,41 @@
 %0A               
+ 
 %7D%0A
+      
       %7D%0A%0A      f
@@ -1147,24 +1147,30 @@
          %7D%0A%0A
+      
       for (i
@@ -1194,32 +1194,40 @@
  i++) %7B%0A        
+   
+     
 for (int j = 1; 
@@ -1233,32 +1233,42 @@
  j %3C= n; j++) %7B%0A
+          
           int k 
@@ -1286,24 +1286,34 @@
 ;%0A          
+  
+        
 dp%5Bi%5D%5Bj%5D = (
@@ -1376,16 +1376,30 @@
         
+        
+      
 %7C%7C (s2.c
@@ -1457,19 +1457,39 @@
     
-%7D%0A      %7D%0A%0A
+        %7D%0A            %7D%0A%0A      
     
@@ -1511,16 +1511,22 @@
 n%5D;%0A    
-%7D%0A
+    %7D%0A  
   %7D%0A%7D%0A

refactor 97