Interleaving String

This problem really took me too much time. I tried recursion and loop methods, but both get TLE. What I initially thought was that: usually we may meet 4 cases: 1) kth char of s3 is same as ith of s1, while not as jth of s2;2) kth char of s3 is same as jth of s2, while not as ith of s1; 3)  kth char of s3 is same as ith of s1, also same as jth of s2; 4)  kth char of s3 is NOT as same as ith of s1, neither jth of s2. Deal with above 4 cases differently, then we can do our job. But this idea always run out of time.

After taking a look at others' code in Leecode community, I finally realized that this should be solved using DP, like knapsack problem, and thanks to  qingjinlyc for his clear explanation. 

Now, let me just explain a little bit. 

One thing we need to be clear about is rslt[i][j] indicates whether s3.substring(0,i+j) is interleaving string of s1.substring(0,i) and s2.substring(0,j). In other words, to determine whether s3.substring(0,i+j) can be interleaving of s1.substring(0,i) and s2.substring(0,j), we need to find a "true" way from (0,0) of matrix to (i,j). Now lets simplify this problem into the smallest one. Assume I want to know whether (i,j) is true, how can I get the answer? I will take a look at left side and above side of (i,j), i.e. (i-1,j) and (i, j -1). If (i-1,j) is true and s3.charAt(i+j-1) == s1.charAt(i-1) (Be careful here, i and j starts from 1, so we need to minus 1), then this could be a valid "true way" to (i,j), similar case with s2. So we can solve this problem in this way.
 

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() != 0 && s2.length() != 0 && (s1.length()+s2.length() != s3.length())) return false;
        if (s1.length() != 0 && s2.length() == 0){
            if(s1.equals(s3)) return true;
            else return false;
        }
        if (s1.length() == 0 && s2.length() != 0){
            if(s2.equals(s3)) return true;
            else return false;
        }
        if(s1.length() == 0 && s2.length() == 0){
            if(s3.length() == 0) return true;
            else return false;
        }

        boolean[][] rslt = new boolean[s1.length()+1][s2.length()+1];
        rslt[0][0] = true;
        for(int i = 1; i<=s1.length();i++){
            rslt[i][0] = s1.substring(0,i).equals(s3.substring(0,i)) ;
        }
        for(int j = 1; j<=s2.length();j++){
            rslt[0][j] = s2.substring(0,j).equals(s3.substring(0,j));
        }
     
        for(int i= 1;i <=s1.length();i++){
            for(int j = 1; j<=s2.length();j++){
                rslt[i][j] = ((s3.charAt(i+j-1)==s1.charAt(i-1) && rslt[i-1][j]) ||
                (s3.charAt(i+j-1)==s2.charAt(j-1) && rslt[i][j-1]));
            }
        }
        return rslt[s1.length()][s2.length()];
 
    }
 
}