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

time or better

Think

• Two sequence DP, 2-D memorized boolean array
• memo[i][j] means from word1(1,i) and word2(1,j) can form the word3(1, i+j)
• Initial the case memo[0][j] and memo[i][0] is false and memo[0][0] should be true.
• Pass through i from 0 to word1.length and j from 0 to word2.length, check if word3[i+j-1]== word2[j-1] or word3[i+j-1]== word1[i-1]
• We also have to make sure when word3[i+j-1]== word2[j-1], the memo[i][j-1] should be true or word3[i+j-1]== word1[i-1], the memo[i-1][j] should be true
• Get the memo[len1][len2] as the final boolean result

Solution

    /**
     * Determine whether s3 is formed by interleaving of s1 and s2.
     * @param s1, s2, s3: As description.
     * @return: true or false.
     */
    public boolean isInterleave(String s1, String s2, String s3) {

        if(s1 == null || s2 == null)
            return false;
        if(s1.length() + s2.length() != s3.length())
            return false;

        boolean[][] memo = new boolean[s1.length() + 1][s2.length() + 1];
        for(int i = 0; i <= s1.length(); i++) {
            for(int j = 0; j <= s2.length(); j++) {
                if(i == 0 && j == 0)
                    memo[i][j] = true;
                else{
                    if(i > 0 && s1.charAt(i - 1) == s3.charAt(i + j - 1))
                        memo[i][j] = memo[i - 1][j];
                    if(j > 0 &&s2.charAt(j - 1) == s3.charAt(i + j - 1))
                        memo[i][j] |= memo[i][j - 1];
                }
            }
        }

        return memo[s1.length()][s2.length()];
    }