97. Interleaving String (Medium)

Problem

Given strings s1, s2, and s3, return whether s3 is formed by interleaving s1 and s2, picking characters in order from either string. |s3| must equal |s1| + |s2|.

Example

• s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" → true
• s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" → false

LeetCode 97 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Recursive

f(i, j) = can s3[:i + j] be formed by s1[:i] and s2[:j]?

Python

def is_interleave(s1, s2, s3):
    if len(s1) + len(s2) != len(s3):   # L1: O(1) length guard
        return False
    def f(i, j):
        k = i + j                       # L2: O(1) current s3 index
        if k == len(s3):               # L3: O(1) base case: consumed all of s3
            return True
        if i < len(s1) and s1[i] == s3[k] and f(i + 1, j):   # L4: try s1 branch
            return True
        if j < len(s2) and s2[j] == s3[k] and f(i, j + 1):   # L5: try s2 branch
            return True
        return False
    return f(0, 0)

TypeScript

function isInterleave(s1: string, s2: string, s3: string): boolean {
    if (s1.length + s2.length !== s3.length) return false;     // L1: O(1) length guard
    function f(i: number, j: number): boolean {
        const k = i + j;                                        // L2: O(1) current s3 index
        if (k === s3.length) return true;                       // L3: O(1) base case
        if (i < s1.length && s1[i] === s3[k] && f(i + 1, j)) return true;  // L4: try s1
        if (j < s2.length && s2[j] === s3[k] && f(i, j + 1)) return true;  // L5: try s2
        return false;
    }
    return f(0, 0);
}

Go

func isInterleave(s1 string, s2 string, s3 string) bool {
    if len(s1)+len(s2) != len(s3) { return false } // L1: O(1) length guard
    var f func(i, j int) bool
    f = func(i, j int) bool {
        k := i + j                                              // L2: O(1) current s3 index
        if k == len(s3) { return true }                        // L3: O(1) base case
        if i < len(s1) && s1[i] == s3[k] && f(i+1, j) { return true } // L4: try s1
        if j < len(s2) && s2[j] == s3[k] && f(i, j+1) { return true } // L5: try s2
        return false
    }
    return f(0, 0)
}

Swift

final class Solution {
    func isInterleave(_ s1: String, _ s2: String, _ s3: String) -> Bool {
        let a = Array(s1), b = Array(s2), c = Array(s3)
        guard a.count + b.count == c.count else { return false }
        func solve(_ i: Int, _ j: Int) -> Bool {
            if i + j == c.count { return true }
            return (i < a.count && a[i] == c[i + j] && solve(i + 1, j)) || (j < b.count && b[j] == c[i + j] && solve(i, j + 1))
        }
        return solve(0, 0)
    }
}

Where the time goes, line by line

Variables: m = len(s1), n = len(s2).

Line	Per-call cost	Times executed	Contribution
L1 (length check)	$O(1)$	1	$O(1)$
L2-L3 (index + base)	$O(1)$	per call	$O(1)$ each
L4, L5 (two recursive branches)	$O(1)$ work + up to 2 calls	$O(2^{m+n})$ call tree	$O(2^{m+n})$ ← dominates

At each step, both s1[i] and s2[j] might match s3[k], spawning two branches. Without caching the same (i, j) is recomputed many times.

Complexity

• Time: $O(2^{m+n})$, driven by L4/L5 double-branching on ambiguous matches.
• Space: $O(m + n)$ recursion depth.

Approach 2: Top-down memoized

Python

from functools import lru_cache

def is_interleave(s1, s2, s3):
    if len(s1) + len(s2) != len(s3):   # L1: O(1) length guard
        return False
    @lru_cache(maxsize=None)            # L2: cache decorator
    def f(i, j):
        k = i + j                       # L3: O(1)
        if k == len(s3):               # L4: O(1) base case
            return True
        if i < len(s1) and s1[i] == s3[k] and f(i + 1, j):   # L5: O(1) with cache
            return True
        if j < len(s2) and s2[j] == s3[k] and f(i, j + 1):   # L6: O(1) with cache
            return True
        return False
    return f(0, 0)

TypeScript

function isInterleave(s1: string, s2: string, s3: string): boolean {
    if (s1.length + s2.length !== s3.length) return false;
    const memo: Map<string, boolean> = new Map();
    function f(i: number, j: number): boolean {
        const key = `${i},${j}`;
        if (memo.has(key)) return memo.get(key)!;
        const k = i + j;
        if (k === s3.length) { memo.set(key, true); return true; }
        let result = false;
        if (i < s1.length && s1[i] === s3[k] && f(i + 1, j)) result = true;
        if (!result && j < s2.length && s2[j] === s3[k] && f(i, j + 1)) result = true;
        memo.set(key, result);
        return result;
    }
    return f(0, 0);
}

Where the time goes, line by line

Variables: m = len(s1), n = len(s2).

Line	Per-call cost	Times executed	Contribution
L1-L2 (guard + cache)	$O(1)$	1	$O(1)$
L3-L4 (index + base)	$O(1)$	once per unique (i,j)	$O(m · n)$ total
L5, L6 (recursive calls, cache hits after first)	$O(1)$ per call	at most (m+1)(n+1) states	$O(m · n)$ ← dominates

With memoization each (i, j) is computed once. Short-circuit evaluation means the second branch at L6 is only evaluated if L5 returns False.

Complexity

• Time: $O(m · n)$, driven by L5/L6 across all unique (i,j) states.
• Space: $O(m · n)$ memo table.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    func isInterleave(_ s1: String, _ s2: String, _ s3: String) -> Bool {
        let a = Array(s1), b = Array(s2), c = Array(s3)
        guard a.count + b.count == c.count else { return false }
        var memo: [String: Bool] = [:]
        func solve(_ i: Int, _ j: Int) -> Bool {
            if i + j == c.count { return true }
            let key = "\(i):\(j)"; if let value = memo[key] { return value }
            let value = (i < a.count && a[i] == c[i + j] && solve(i + 1, j)) || (j < b.count && b[j] == c[i + j] && solve(i, j + 1))
            memo[key] = value; return value
        }
        return solve(0, 0)
    }
}

Approach 3: Bottom-up 2-D DP

dp[i][j] = can s3[:i + j] be formed from s1[:i] and s2[:j]?

Python

def is_interleave(s1, s2, s3):
    m, n = len(s1), len(s2)             # L1: O(1)
    if m + n != len(s3):               # L2: O(1) length guard
        return False
    dp = [[False] * (n + 1) for _ in range(m + 1)]  # L3: O(m*n) table init
    dp[0][0] = True                    # L4: O(1) base case
    for i in range(m + 1):            # L5: outer loop O(m)
        for j in range(n + 1):        # L6: inner loop O(n)
            if i == 0 and j == 0:
                continue
            k = i + j - 1             # L7: O(1) s3 index
            if i > 0 and s1[i - 1] == s3[k] and dp[i - 1][j]:    # L8: O(1) from-s1 check
                dp[i][j] = True
            if not dp[i][j] and j > 0 and s2[j - 1] == s3[k] and dp[i][j - 1]:  # L9: O(1) from-s2 check
                dp[i][j] = True
    return dp[m][n]                    # L10: O(1) answer

TypeScript

function isInterleave(s1: string, s2: string, s3: string): boolean {
    const m = s1.length, n = s2.length;
    if (m + n !== s3.length) return false;                         // L2: O(1) length guard
    const dp: boolean[][] = Array.from({ length: m + 1 }, () =>
        new Array(n + 1).fill(false));                             // L3: O(m*n) table init
    dp[0][0] = true;                                               // L4: O(1) base case
    for (let i = 0; i <= m; i++) {                                 // L5: outer loop O(m)
        for (let j = 0; j <= n; j++) {                             // L6: inner loop O(n)
            if (i === 0 && j === 0) continue;
            const k = i + j - 1;                                   // L7: O(1) s3 index
            if (i > 0 && s1[i - 1] === s3[k] && dp[i - 1][j])    // L8: O(1) from-s1
                dp[i][j] = true;
            if (!dp[i][j] && j > 0 && s2[j - 1] === s3[k] && dp[i][j - 1])  // L9: from-s2
                dp[i][j] = true;
        }
    }
    return dp[m][n];                                               // L10: O(1) answer
}

Go

func isInterleave(s1 string, s2 string, s3 string) bool {
    m, n := len(s1), len(s2)
    if m+n != len(s3) { return false }              // L2: O(1) length guard
    dp := make([][]bool, m+1)
    for i := range dp { dp[i] = make([]bool, n+1) } // L3: O(m*n) table init
    dp[0][0] = true                                  // L4: O(1) base case
    for i := 0; i <= m; i++ {                        // L5: outer loop O(m)
        for j := 0; j <= n; j++ {                    // L6: inner loop O(n)
            if i == 0 && j == 0 { continue }
            k := i + j - 1                           // L7: O(1) s3 index
            if i > 0 && s1[i-1] == s3[k] && dp[i-1][j] { dp[i][j] = true } // L8
            if !dp[i][j] && j > 0 && s2[j-1] == s3[k] && dp[i][j-1] { dp[i][j] = true } // L9
        }
    }
    return dp[m][n]                                  // L10: O(1) answer
}

Where the time goes, line by line

Variables: m = len(s1), n = len(s2).

Line	Per-call cost	Times executed	Contribution
L1-L4 (init)	$O(1)$ or $O(m·n)$	1	$O(m · n)$
L5+L6 (double loop)	$O(1)$ body	(m+1)(n+1)	$O(m · n)$ ← dominates
L7-L9 (cell fill)	$O(1)$	once per cell	included above

Each cell requires at most two $O(1)$ lookups. The double loop at L5/L6 drives the total cost.

Complexity

• Time: $O(m · n)$, driven by L5/L6 (the full double loop).
• Space: $O(m · n)$. Can be reduced to $O(min(m, n)$) via rolling array.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    func isInterleave(_ s1: String, _ s2: String, _ s3: String) -> Bool {
        let a = Array(s1), b = Array(s2), c = Array(s3)
        guard a.count + b.count == c.count else { return false }
        var dp = Array(repeating: Array(repeating: false, count: b.count + 1), count: a.count + 1); dp[0][0] = true
        for i in 0...a.count { for j in 0...b.count where i + j > 0 { dp[i][j] = (i > 0 && dp[i - 1][j] && a[i - 1] == c[i + j - 1]) || (j > 0 && dp[i][j - 1] && b[j - 1] == c[i + j - 1]) } }
        return dp[a.count][b.count]
    }
}

Summary

Approach	Time	Space
Naive recursion	$O(2^{m+n})$	$O(m + n)$
Top-down memo	$O(m · n)$	$O(m · n)$
Bottom-up 2-D DP	$O(m · n)$	$O(m · n)$

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_097.py and run.
# Uses the canonical implementation (Approach 3: bottom-up 2-D DP).

def is_interleave(s1, s2, s3):
    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 j == 0:
                continue
            k = i + j - 1
            if i > 0 and s1[i - 1] == s3[k] and dp[i - 1][j]:
                dp[i][j] = True
            if not dp[i][j] and j > 0 and s2[j - 1] == s3[k] and dp[i][j - 1]:
                dp[i][j] = True
    return dp[m][n]

def _run_tests():
    # problem statement examples
    assert is_interleave("aabcc", "dbbca", "aadbbcbcac") == True
    assert is_interleave("aabcc", "dbbca", "aadbbbaccc") == False
    # edge: empty strings
    assert is_interleave("", "", "") == True
    assert is_interleave("a", "", "a") == True
    assert is_interleave("", "b", "b") == True
    # wrong length
    assert is_interleave("a", "b", "abc") == False
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function isInterleave(s1: string, s2: string, s3: string): boolean {
    const m = s1.length, n = s2.length;
    if (m + n !== s3.length) return false;
    const dp: boolean[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(false));
    dp[0][0] = true;
    for (let i = 0; i <= m; i++)
        for (let j = 0; j <= n; j++) {
            if (i === 0 && j === 0) continue;
            const k = i + j - 1;
            if (i > 0 && s1[i - 1] === s3[k] && dp[i - 1][j]) dp[i][j] = true;
            if (!dp[i][j] && j > 0 && s2[j - 1] === s3[k] && dp[i][j - 1]) dp[i][j] = true;
        }
    return dp[m][n];
}

console.assert(isInterleave("aabcc", "dbbca", "aadbbcbcac") === true);
console.assert(isInterleave("aabcc", "dbbca", "aadbbbaccc") === false);
console.assert(isInterleave("", "", "") === true);
console.assert(isInterleave("a", "", "a") === true);
console.assert(isInterleave("", "b", "b") === true);
console.assert(isInterleave("a", "b", "abc") === false);
console.log("all tests pass");

Go

package main

import "fmt"

func isInterleave(s1 string, s2 string, s3 string) bool {
    m, n := len(s1), len(s2)
    if m+n != len(s3) { return false }
    dp := make([][]bool, m+1)
    for i := range dp { dp[i] = make([]bool, n+1) }
    dp[0][0] = true
    for i := 0; i <= m; i++ {
        for j := 0; j <= n; j++ {
            if i == 0 && j == 0 { continue }
            k := i + j - 1
            if i > 0 && s1[i-1] == s3[k] && dp[i-1][j] { dp[i][j] = true }
            if !dp[i][j] && j > 0 && s2[j-1] == s3[k] && dp[i][j-1] { dp[i][j] = true }
        }
    }
    return dp[m][n]
}

func main() {
    if !isInterleave("aabcc", "dbbca", "aadbbcbcac") { panic("fail") }
    if isInterleave("aabcc", "dbbca", "aadbbbaccc") { panic("fail") }
    if !isInterleave("", "", "") { panic("fail") }
    if !isInterleave("a", "", "a") { panic("fail") }
    if !isInterleave("", "b", "b") { panic("fail") }
    if isInterleave("a", "b", "abc") { panic("fail") }
    fmt.Println("all tests pass")
}

Related data structures

• Strings, 2-D DP over paired indices

Related concepts

• Memoization, the top down cache pattern that keeps recursive structure without repeated work.
• Dynamic Programming, the state and transition model for reusing answers to overlapping subproblems.