Question

link

Stats

Frequency	2
Difficulty	5
Adjusted Difficulty	3
Time to use	--------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is a DP question.

At first look it might look like very easily solved by DFS. It it, but TLE exception.

So, I learnt the idea from this blog. It’s easy to realize this is a very standard DP question.

Solution

Declare a 2-D array for DP, and dp(i)(j) denotes whether it’s possible to construct s3 (of length i+j) by using s1 (of length i) and s2 (of length j).

Only thing needs to mention is the size of dp is (m+1)*(n+1), because i = [0, m] and j = [0, n].

Code

DP solution

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