Problem 31.8 · DP on Strings and SequencesMedium

Interleaving String

What it teaches: A boolean grid over two strings; the third string's position is implied by i + j.

Practise it on judges as “Interleaving String”.

The problem

Return true if s3 is formed by interleaving s1 and s2 (keeping each one's characters in order).

Example 1

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Constraints

0 ≤ s1, s2 ≤ 100

Pattern clues in the wording

→ Merge two sequences preserving order

These clues point to DP on Two Strings: dp[i][j] answers the question for the first i characters of one string and the first j of the other.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        return false;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	s1 = "aabcc" s2 = "dbbca" s3 = "aadbbcbcac"	true
2	s1 = "aabcc" s2 = "dbbca" s3 = "aadbbbaccc"	false
3	s1 = "" s2 = "" s3 = ""	true

From slow to fast

Approaches

1. One-row boolean DP · O(m × n)

One-row boolean DP

Time O(m × n) Space O(n)

ok[j] for the current i; ok[j] = (ok[j] && s1[i − 1] == s3[i + j − 1]) || (ok[j − 1] && s2[j − 1] == s3[i + j − 1]).

Approach 1

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[] ok = new boolean[n + 1];
        for (int i = 0; i <= m; i++)
            for (int j = 0; j <= n; j++) {
                if (i == 0 && j == 0) { ok[0] = true; continue; }
                boolean fromS1 = i > 0 && ok[j] && s1.charAt(i - 1) == s3.charAt(i + j - 1);
                boolean fromS2 = j > 0 && ok[j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1);
                ok[j] = fromS1 || fromS2;
            }
        return ok[n];
    }
}

Verdict: Greedy matching fails; DP handles ties.

Before you submit

Edge cases and common mistakes

Test these inputs

All empty (true)
Lengths don't add up (false)

Mistakes people make

Greedily taking from s1 whenever it matches.

Interview

Follow-up questions

How is this a graph problem?

Command Palette

The problem

Approaches

One-row boolean DP

Edge cases and common mistakes

Follow-up questions