[LeetCode] 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.

解题思路：

DP， 和edit distance有点类似

    public boolean isInterleave(String s1, String s2, String s3) {
           int len1 = s1.length();
           int len2 = s2.length();
           
           if(s3.length() != len1 + len2) return false;
           
           boolean[][] match = new boolean[len1+1][len2+1];
           
           for(int i = 0; i <= len1; i++){
               for(int j = 0; j <= len2; j++){
                   if(i == 0 && j == 0){
                       match[i][j] = true;
                   }else{
                       if(j > 0 && s3.charAt(i+j-1) == s2.charAt(j-1)) match[i][j] = match[i][j] || match[i][j-1];
                       if(i > 0 && s3.charAt(i+j-1) == s1.charAt(i-1)) match[i][j] = match[i][j] || match[i-1][j];
                   }
               }
           }
           
           return match[len1][len2];
    }