139. Word Break

At a Glance

Topic: Array
Pattern: Analyze Pattern
Difficulty: Medium
LeetCode: 139

Problem Statement

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

Input: s = "leetcode", wordDict = ["leet","code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen"] Output: true Explanation: Return true because "applepenapple" can be segmented as "apple pen apple". Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] Output: false

Constraints:

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s and wordD...

Approach & Solution Steps

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 JS Solution

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];
}

Edge Cases & Pitfalls

Always consider empty or null inputs.
Watch out for off-by-one index errors.