Interleaving String

MEDIUM✓ CHIP-TIMEDLC #97 — FULL STATEMENT ↗

The drill: Two source strings and a candidate merge — decide whether the candidate could have been built by interleaving the two sources while keeping each source's own character order intact.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

Two source strings and a third candidate string arrive, and the task is to decide whether the candidate could have been built by interleaving the two sources together — weaving their characters into one sequence while keeping each source's own internal character order untouched.

Characters from the two sources can be interleaved in any pattern, switching back and forth as often as needed, but a source's own characters always have to appear in the same order they started in. Every character from both sources has to be used exactly once, with nothing left over.

The output is just yes or no — whether at least one valid interleaving produces the candidate string.

EX 01

s1 = "" · s2 = "" · s3 = ""

→ true

EVERYTHING EMPTY

EX 02

s1 = "a" · s2 = "" · s3 = "a"

→ true

SECOND SOURCE CONTRIBUTES NOTHING

EX 03

s1 = "" · s2 = "b" · s3 = "b"

→ true

FIRST SOURCE CONTRIBUTES NOTHING

the candidate's length must equal the combined length of both sources
strings stay short enough for an O(m·n) table
characters from each source keep their original relative order
the answer is a single true/false

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

If the candidate isn't even the right length, it can't be an interleaving — check that first. Otherwise, having consumed i characters from one source and j from the other always points at one exact position in the candidate: i + j.

HINT 2 THE STRUCTURE

At every step, the next character of the candidate has to come from the next unused character of source one or the next unused character of source two — never from further ahead in either.

HINT 3 ONE STEP FROM THE ANSWER

DP: dp[i][j] = true when the first i+j characters of the candidate can be built from the first i of s1 and first j of s2. It's true if (dp[i-1][j] and s1[i-1] matches) or (dp[i][j-1] and s2[j-1] matches).

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE WEAVE CHECKPATTERN · GRID DP — TWO SOURCESs1 = "ab" · s2 = "cd" · s3 = "acbd"

STEP 1

s1='ab', s2='cd', s3='acbd'. dp[i][j] asks: can the first i+j chars of acbd come from the first i of s1 and first j of s2? dp[0][0]=true trivially.

STEP 1 / 9 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/interleaving-string.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m, n = len(s1), len(s2)
        if m + n != len(s3):
            return False
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True
        for i in range(m + 1):
            for j in range(n + 1):
                if i > 0 and dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]:
                    dp[i][j] = True
                if j > 0 and dp[i][j - 1] and s2[j - 1] == s3[i + j - 1]:
                    dp[i][j] = True
        return dp[m][n]

TIME O(M·N)SPACE O(M·N)PYTHON · RACE PACE · 14 LN

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m, n = len(s1), len(s2)
        if m + n != len(s3):
            return False

        def dfs(i, j):
            k = i + j
            if i == m and j == n:
                return True
            if i < m and s1[i] == s3[k] and dfs(i + 1, j):
                return True
            if j < n and s2[j] == s3[k] and dfs(i, j + 1):
                return True
            return False

        return dfs(0, 0)

TIME O(2^(M+N))SPACE O(M+N)PYTHON · TRAINING PACE · 17 LN

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

TIME O(M·N)SPACE O(M·N)JAVA · RACE PACE · 21 LN

class Solution {
    private String s1, s2, s3;
    private int m, n;

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

    private boolean dfs(int i, int j) {
        int k = i + j;
        if (i == m && j == n) {
            return true;
        }
        if (i < m && s1.charAt(i) == s3.charAt(k) && dfs(i + 1, j)) {
            return true;
        }
        if (j < n && s2.charAt(j) == s3.charAt(k) && dfs(i, j + 1)) {
            return true;
        }
        return false;
    }
}

TIME O(2^(M+N))SPACE O(M+N)JAVA · TRAINING PACE · 30 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED