Word Break

Word Break

What is this problem about?

The "Word Break" problem asks if a given string s can be segmented into a space-separated sequence of one or more dictionary words. You are given a string and a list of words (the dictionary). You can reuse words from the dictionary as many times as needed.

Why is this asked in interviews?

This is one of the most frequently asked "Medium" problems in Silicon Valley. It perfectly illustrates the transition from a naive recursive solution to an optimized Dynamic Programming or BFS solution. Companies like Amazon and LinkedIn use it to check if you understand the "Overlapping Subproblems" property.

Algorithmic pattern used

The standard solution is 1D Dynamic Programming. Let dp[i] be a boolean indicating whether the substring s[0...i] can be broken into dictionary words.

• To compute dp[i], you check all possible split points j < i.
• If dp[j] is true AND s[j...i] is in the dictionary, then dp[i] is true. Alternatively, this can be modeled as a Graph Search (BFS) where indices are nodes and dictionary words are edges.

Example explanation

String: applepie, Dictionary: ["apple", "pie"].

1. dp[0] is True (empty string).
2. dp[5] (apple): dp[0] is True and s[0:5] ("apple") is in dict. So dp[5] = True.
3. dp[8] (applepie): Check split at j=5. dp[5] is True and s[5:8] ("pie") is in dict. So dp[8] = True. Final answer: True.

Common mistakes candidates make

• Inefficient Dictionary Lookups: Not converting the dictionary to a Hash Set for O(1) lookups.
• Redundant Work: Using simple recursion without memoization, leading to O(2^N) complexity.
• Substring range errors: Messing up the start and end indices during string slicing.

Interview preparation tip

This is a foundational DP problem. Once you master "Word Break," you'll find it easier to solve other partitioning problems like "Palindrome Partitioning" or "Matrix Chain Multiplication."