Word Break

The Word Break problem is a cornerstone dynamic programming challenge that appears frequently in coding interviews. On the surface, the task seems like a straightforward dictionary lookup exercise. However, as soon as you try to draw out all valid segmentations of a string, the real complexity becomes clear.

This problem tests your ability to recognize overlapping subproblems, construct a bottom-up DP table, and reason about prefix matching efficiently.

Problem

You are given:

• A string s
• A list of valid words called wordDict

Your task:

Return true if s can be segmented into a space-separated sequence of one or more dictionary words. Otherwise, return false.

Rules:

• Words may be reused any number of times.
• The order of segmentation must follow the string from left to right.
• All dictionary words are non-empty.

Example

Input:

s = "leetcode"

wordDict = ["leet", "code"]

Output:

true

Explanation:

“leetcode” can be segmented as “leet code”.

Input:

s = "applepenapple"

wordDict = ["apple", "pen"]

Output:

true

Explanation:

You can segment it as “apple pen apple”.

Input:

s = "catsandog"

wordDict = ["cats", "dog", "sand", "and", "cat"]

Output:

false

No valid segmentation covers the whole string.

Solution

Trying all segmentations directly leads to an exponential explosion. Instead, the key is to ask:

“For every index i in the string, can we reach i using valid dictionary words?”

This is a classic bottom-up dynamic programming problem.

We define a DP array:

dp[i] = True if s[:i] can be segmented using dictionary words

Your goal is to compute dp[len(s)].

Key idea

For each position i in the string:

• Scan backwards j < i
• Check:
  • If dp[j] is True (meaning s[:j] is segmentable), and
  • If s[j:i] is a dictionary word

If both are true, set dp[i] = True and break.

This ensures you build the segmentation from left to right, verifying at each step whether the prefix is valid.

Why this works

This DP approach works because:

• Any segmentation of s must break at some index j before i
• If s[:j] is segmentable AND s[j:i] is a valid word, then s[:i] is segmentable
• You avoid recomputation by storing results in dp
• All splits are considered implicitly through nested loops

Time complexity is:

• \( O(n²) \) for checking all substrings
• \( O(1) \) dictionary lookups using a hash set

Space complexity: \( O(n) \)

Algorithm outline

1. Convert wordDict into a hash set for \( O(1) \) lookup.
2. Create a DP array dp of size n + 1, initialized to False.
3. Set dp[0] = True since an empty prefix is trivially segmentable.
4. For each i from 1 to n:
   • For each j from 0 to i:
     • If dp[j] is True and s[j:i] is in the dictionary, set dp[i] = True and break.
5. Return dp[n].

Sample implementation (Python)

Optimization: limit substring checks

You can reduce inner loop checks by tracking the maximum word length in the dictionary, preventing unnecessary substring checks.

Alternative approach: recursion + memoization

You can solve the problem top-down with DFS and memoization.
However:

• It can be slower due to recursion overhead.
• DP is more predictable and straightforward.

Interview insight

The Word Break problem is a favorite for testing:

• Your understanding of dynamic programming
• Ability to think in terms of prefix validity
• Efficient lookup using hash sets
• Recognition of overlapping subproblems
• Clean reasoning about how segmentations propagate

It’s also foundational: more complex variants (like Word Break II, which requires generating all segmentations) build directly on these ideas.