97. Interleaving String

At a Glance

Topic: dp-2d
Pattern: Dynamic Programming (two-string matching with merge order)
Difficulty: Medium
Companies: Google, Amazon, Apple, Microsoft, Bloomberg
Frequency: High
LeetCode: 97

Problem (one-liner)

Given s1, s2, and s3, determine whether s3 can be formed by interleaving s1 and s2 while preserving each string’s internal character order. Input: three strings. Output: boolean.

Recognition Cues

“Interleave” two strings into a third
Length must satisfy len(s3) == len(s1) + len(s2)
At each step take next from s1 or s2 if it matches s3

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute force — DFS all branches — exponential.
Better — reachable[i][j] whether first i+j of s3 matches first i of s1 and first j of s2 — O(m*n) time / O(m*n) space.
Optimal — 1D rolling on shorter dimension — O(m*n) time / O(min(m,n)) space. <- pick this in interview.

Optimal Solution

Go

package main

func isInterleaveTable(s1 string, s2 string, s3 string) bool {
	length1 := len(s1)
	length2 := len(s2)
	if length1+length2 != len(s3) {
		return false
	}
	reachable := make([][]bool, length1+1)
	for index := range reachable {
		reachable[index] = make([]bool, length2+1)
	}
	reachable[0][0] = true
	for prefix1 := 0; prefix1 <= length1; prefix1++ {
		for prefix2 := 0; prefix2 <= length2; prefix2++ {
			if prefix1 == 0 && prefix2 == 0 {
				continue
			}
			position := prefix1 + prefix2 - 1
			matchFromFirst := false
			if prefix1 > 0 && reachable[prefix1-1][prefix2] && s1[prefix1-1] == s3[position] {
				matchFromFirst = true
			}
			matchFromSecond := false
			if prefix2 > 0 && reachable[prefix1][prefix2-1] && s2[prefix2-1] == s3[position] {
				matchFromSecond = true
			}
			reachable[prefix1][prefix2] = matchFromFirst || matchFromSecond
		}
	}
	return reachable[length1][length2]
}

func isInterleave(s1 string, s2 string, s3 string) bool {
	length1 := len(s1)
	length2 := len(s2)
	if length1+length2 != len(s3) {
		return false
	}
	previous := make([]bool, length2+1)
	current := make([]bool, length2+1)
	previous[0] = true
	for prefix2 := 1; prefix2 <= length2; prefix2++ {
		previous[prefix2] = previous[prefix2-1] && s2[prefix2-1] == s3[prefix2-1]
	}
	for prefix1 := 1; prefix1 <= length1; prefix1++ {
		current[0] = previous[0] && s1[prefix1-1] == s3[prefix1-1]
		for prefix2 := 1; prefix2 <= length2; prefix2++ {
			position := prefix1 + prefix2 - 1
			fromFirst := previous[prefix2] && s1[prefix1-1] == s3[position]
			fromSecond := current[prefix2-1] && s2[prefix2-1] == s3[position]
			current[prefix2] = fromFirst || fromSecond
		}
		copy(previous, current)
	}
	return previous[length2]
}

JavaScript

function isInterleave(s1, s2, s3) {
	const length1 = s1.length;
	const length2 = s2.length;
	if (length1 + length2 !== s3.length) return false;
	const previous = new Array(length2 + 1).fill(false);
	previous[0] = true;
	for (let prefix2 = 1; prefix2 <= length2; prefix2++) {
		previous[prefix2] =
			previous[prefix2 - 1] && s2[prefix2 - 1] === s3[prefix2 - 1];
	}
	for (let prefix1 = 1; prefix1 <= length1; prefix1++) {
		const current = new Array(length2 + 1).fill(false);
		current[0] = previous[0] && s1[prefix1 - 1] === s3[prefix1 - 1];
		for (let prefix2 = 1; prefix2 <= length2; prefix2++) {
			const position = prefix1 + prefix2 - 1;
			const fromFirst =
				previous[prefix2] && s1[prefix1 - 1] === s3[position];
			const fromSecond =
				current[prefix2 - 1] && s2[prefix2 - 1] === s3[position];
			current[prefix2] = fromFirst || fromSecond;
		}
		for (let index = 0; index <= length2; index++) {
			previous[index] = current[index];
		}
	}
	return previous[length2];
}