Interleaving String

Source

• lintcode: Interleaving String

Given three strings: s1, s2, s3, determine whether s3 is formed by the interleaving of s1 and s2.

Example
For s1 = "aabcc", s2 = "dbbca"

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
Challenge
O(n2) time or better

Java

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {  
        int n1=s1.length(), n2=s2.length(), n3=s3.length();    
        if (n1 + n2 != n3) return false;    

        boolean[][] match = new boolean[n1+1][n2+1];    
        // initialize the first row and first column    
        match[0][0] = true;    
        for (int i=0; i < n1; ++i) {    
            match[i+1][0] = (s1.charAt(i) == s3.charAt(i)) && match[i][0];    
        }    
        for (int i=0; i < n2; ++i) {    
            match[0][i+1] = (s2.charAt(i) == s3.charAt(i)) && match[0][i];    
        }    
        // fill up the table    
        for (int i=0; i < n1; ++i) {    
            for (int j=0; j < n2; ++j) {    
                if ((match[i][j+1] && s3.charAt(i+j+1)==s1.charAt(i))    
                || (match[i+1][j] && s3.charAt(i+j+1)==s2.charAt(j))) {    
                    match[i+1][j+1] = true;    
                }    
            }    
        }    
        return match[n1][n2];    
    }  
}