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

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.

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

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 — 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"]

end	tries from reachable starts	reachable[end]
0	—	true
4	`s[0:4]="leet"` in dict	true
8	`s[4:8]="code"` in dict	true

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.