Find if a string is interleaved of two other strings

The problem, simply

You get three strings s1, s2 and s3. Can s3 be made by weaving s1 and s2 together? Weaving means: take letters one at a time, each time from the front of s1 or the front of s2, until both are used up. The letters of s1 stay in their order, and so do the letters of s2.

Return true or false.

A story to remember it

Picture it

Examples

Way 1: the simple way

Walk through s3 one letter at a time, keeping i (letters used from s1) and j (letters used from s2). The next letter of s3 is at i + j.

1. If i + j reached the end of s3, check that both s1 and s2 are used up.
2. If the next letter matches s1[i], try taking it from s1.
3. If that fails and the letter matches s2[j], try taking it from s2.

class Solution {
    boolean can(String s1, String s2, String s3, int i, int j) {
        if (i + j == s3.length()) return i == s1.length() && j == s2.length();
        char c = s3.charAt(i + j);
        boolean ok = false;
        if (i < s1.length() && s1.charAt(i) == c) {
            ok = can(s1, s2, s3, i + 1, j);         // take it from s1
        }
        if (!ok && j < s2.length() && s2.charAt(j) == c) {
            ok = can(s1, s2, s3, i, j + 1);         // or take it from s2
        }
        return ok;
    }

    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) return false;
        return can(s1, s2, s3, 0, 0);
    }
}

How long it takes: whenever both decks match, the work splits in two, so it can reach O(2^(m+n)). Extra room: the chain of calls, O(m + n).

Way 2: the clever way

The state is only (i, j), so there are (m + 1) * (n + 1) different questions. Put them in a table dp and fill it row by row.

1. dp[0][0] = true.
2. For each box, let c = s3[i + j - 1].
3. dp[i][j] is true if (dp[i-1][j] and s1[i-1] == c) or (dp[i][j-1] and s2[j-1] == c).
4. The answer is dp[m][n].

Think of it as a walk on a grid from the top left to the bottom right. A step down uses a letter of s1, a step right uses a letter of s2, and every step must match the next letter of s3.

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length();
        if (m + n != s3.length()) return false;
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;                                  // nothing makes nothing
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0 && j == 0) continue;
                char c = s3.charAt(i + j - 1);            // the letter we need now
                boolean fromS1 = i > 0 && dp[i - 1][j] && s1.charAt(i - 1) == c;
                boolean fromS2 = j > 0 && dp[i][j - 1] && s2.charAt(j - 1) == c;
                dp[i][j] = fromS1 || fromS2;
            }
        }
        return dp[m][n];
    }
}

How long it takes: one quick check per box, O(m * n). Extra room: the table, O(m * n). A box only needs the box above and the box to the left, so one row of n + 1 booleans is enough for O(n) room.

Watch out for

• Check m + n == s3.length() first. Otherwise i + j - 1 can run past the end of s3.
• The letter for box (i, j) is s3[i + j - 1], not s3[i + j].
• Fill the first row and column too. The loop above handles them with the i > 0 and j > 0 checks.

What interviewers ask next

• Use only O(min(m, n)) memory. Keep one row: dp[j] = (dp[j] && s1[i-1] == c) || (dp[j-1] && s2[j-1] == c), and make the shorter string the columns.
• Print one way to weave them. Walk back from (m, n) through true boxes, as in the last frame above.
• Count the number of ways to weave? Same table with numbers instead of true and false: add the two incoming counts.
• Three strings woven into a fourth? The state becomes (i, j, k), a 3D table of size (a + 1)(b + 1)(c + 1).
• Can memoized recursion replace the table? Yes. Cache can(i, j) in a Boolean[][]. Same O(m * n) time.

Remember this

Grown-up words: weaving is interleaving, the decks keep their order so each one is a subsequence of s3, the chart is a 2D DP table, and the down and right steps make it a path problem on a grid.