139. Word Break

At a Glance

• Topic: dp-1d
• Pattern: Dynamic Programming on string segmentation; Trie for dictionary lookup / pruning
• Difficulty: Medium
• Companies: Google, Amazon, Facebook, Microsoft, Bloomberg
• Frequency: Very High
• LeetCode: 139

Problem (one-liner)

Given string s and a dictionary of words, determine if s can be segmented into a sequence of one or more dictionary words without reordering characters. Input: s, wordDict. Output: boolean.

Core Basics

• Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
• Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
• Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

• Why brute hurts: name the repeated work or state explosion in one sentence.
• Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

• One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

• “Break into words from dictionary”
• Dictionary lookup repeatedly → hash set for O(1) membership
• Prefix property: if s[0:k] works and remainder starts with a word, continue

Study Pattern (SDE3+)

• 0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

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

Approaches

• Brute force — try all splits — exponential.
• Better — BFS/DFS with memo on start index — O(n^3) worst with substring checks, O(n * m) with clever hashing.
• Optimal — reachable[end] boolean DP — O(n^2 * average_word_check) time; with trie can prune. <- pick this in interview.

Optimal Solution

Go

package main

func wordBreakTable(s string, wordDict []string) bool {
	length := len(s)
	wordSet := make(map[string]struct{}, len(wordDict))
	for _, word := range wordDict {
		wordSet[word] = struct{}{}
	}
	reachable := make([]bool, length+1)
	reachable[0] = true
	for end := 1; end <= length; end++ {
		for start := 0; start < end; start++ {
			if !reachable[start] {
				continue
			}
			segment := s[start:end]
			if _, exists := wordSet[segment]; exists {
				reachable[end] = true
				break
			}
		}
	}
	return reachable[length]
}

func wordBreak(s string, wordDict []string) bool {
	length := len(s)
	wordSet := make(map[string]struct{}, len(wordDict))
	maxWord := 0
	for _, word := range wordDict {
		wordSet[word] = struct{}{}
		if len(word) > maxWord {
			maxWord = len(word)
		}
	}
	reachable := make([]bool, length+1)
	reachable[0] = true
	for start := 0; start < length; start++ {
		if !reachable[start] {
			continue
		}
		limit := start + maxWord
		if limit > length {
			limit = length
		}
		for end := start + 1; end <= limit; end++ {
			segment := s[start:end]
			if _, exists := wordSet[segment]; exists {
				reachable[end] = true
			}
		}
	}
	return reachable[length]
}

JavaScript

function wordBreakTable(s, wordDict) {
	const length = s.length;
	const wordSet = new Set(wordDict);
	const reachable = new Array(length + 1).fill(false);
	reachable[0] = true;
	for (let end = 1; end <= length; end++) {
		for (let start = 0; start < end; start++) {
			if (!reachable[start]) continue;
			const segment = s.slice(start, end);
			if (wordSet.has(segment)) {
				reachable[end] = true;
				break;
			}
		}
	}
	return reachable[length];
}

function wordBreak(s, wordDict) {
	const length = s.length;
	const wordSet = new Set(wordDict);
	let maxWord = 0;
	for (const word of wordDict) {
		maxWord = Math.max(maxWord, word.length);
	}
	const reachable = new Array(length + 1).fill(false);
	reachable[0] = true;
	for (let start = 0; start < length; start++) {
		if (!reachable[start]) continue;
		const limit = Math.min(length, start + maxWord);
		for (let end = start + 1; end <= limit; end++) {
			const segment = s.slice(start, end);
			if (wordSet.has(segment)) {
				reachable[end] = true;
			}
		}
	}
	return reachable[length];
}

Walkthrough

Input: s = "leetcode", wordDict = ["leet","code"]

Trie note: build a trie of wordDict and walk s from each start to avoid slicing every substring if you need micro-optimizations; same DP skeleton.

Edge Cases

• Empty s (if allowed) → often true
• s exactly one word in dict
• No valid segmentation → false

Pitfalls

• Using permutations (order is fixed left-to-right)
• Recomputing dict lookup as O(dict size) every time — use set/trie

Similar Problems

• 091. Decode Ways — digit decoding partition.
• 322. Coin Change — composition counting with numeric weights.
• 300. Longest Increasing Subsequence — another 1D “build answer left to right” DP (different rule).

Variants

• Return all segmentations (Word Break II).
• Add Trie class from Trie pattern for large dictionaries.

Mind-Map Tags

#word-break #trie-optional #segmentation-dp #dictionary #medium