1 public class Solution {
 2     public boolean isInterleave(String s1, String s2, String s3) {
 3         int len1 = s1.length(), len2= s2.length(), len3 = s3.length();
 4         if(len1 == 0 || len2 == 0)
 5             return s3.equals(s1) || s3.equals(s2);
 6         if(len3 != len1 + len2)
 7             return false;
 8         int[][] paths = new int[len1 + 1][len2 + 1];
 9         paths[0][0] = 1;
10         for(int i = 1; i < len2 + 1; ++i)
11             paths[0][i] = (s2.charAt(i - 1) == s3.charAt(i - 1)) ? 1 : 0;
12         for(int i = 1; i < len1 + 1; ++i)
13             paths[i][0] = (s1.charAt(i - 1) == s3.charAt(i - 1)) ? 1 : 0;
14         for(int i = 1; i < len1 + 1; ++i){
15             for(int j = 1; j < len2 + 1; ++j){
16                 if(paths[i][j - 1] == 1 && s3.charAt(i + j - 1) == s2.charAt(j - 1))
17                     paths[i][j] = 1;
18                 else if(paths[i - 1][j] == 1 && s3.charAt(i + j - 1) == s1.charAt(i - 1))
19                     paths[i][j] = 1;
20                 else
21                     paths[i][j] = 0;
22             }            
23         }         
24         return (paths[len1][len2] == 1)? true : false;        
25     }
26 }