Word Break

Word Break requires scanning the input string and checking subsegments against a dictionary stored in a hash set. The problem benefits from dynamic programming to avoid redundant checks and efficiently handle repeated word reuse. A recursive or iterative DP table tracks valid splits, while hash lookups ensure O(1) word existence checks, making it suitable for medium-complexity array and string manipulation patterns.

Problem Statement

Given a string s and a word dictionary wordDict, determine whether s can be split into one or more words from wordDict. The same dictionary word can be used multiple times, and all segments must appear in wordDict. Use array scanning to explore possible segmentations and hash lookups to verify word presence quickly for each substring considered.

Implement a solution that returns true if s can be completely segmented into dictionary words, otherwise false. Pay attention to overlapping segment possibilities, repeated word usage, and efficient substring checking using DP to minimize redundant scans.

Examples

Example 1

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

Output: true

Return true because "leetcode" can be segmented as "leet code".

Example 2

Input: s = "applepenapple", wordDict = ["apple","pen"]

Output: true

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

Example details omitted.

Constraints

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s and wordDict[i] consist of only lowercase English letters.
• All the strings of wordDict are unique.

Solution Approach

Dynamic Programming with Hash Lookup

Initialize a boolean DP array of size n+1 where n is the length of s, setting dp[0] = true. Iterate through s, for each index i, scan all j < i and check if dp[j] is true and s[j:i] exists in wordDict (hash set). Mark dp[i] true if both conditions hold. This approach ensures all valid splits are considered without recomputation and leverages hash lookups for constant-time substring verification, reducing the overhead of repeated dictionary scans.

Recursive Memoization

Implement a recursive function that attempts to segment s from the current index. For each recursion, iterate over possible end indices, checking if the substring exists in wordDict. Cache results for each start index to avoid redundant work. This memoization ensures that repeated subproblems are computed only once, effectively combining array scanning for substring splits with hash-based verification for dictionary membership. Recursion mirrors DP but can be more intuitive for handling variable-length segments.

Trie-Based Optimization

Build a trie from wordDict to allow prefix-based early termination. While scanning the string s, attempt to match substrings against the trie. If a path in the trie ends at a valid word, recursively or iteratively continue from the next index. This reduces unnecessary scanning of substrings that cannot lead to a valid segmentation. Combine with DP or memoization to store results of previous indices, preserving O(1) word lookup speed and minimizing repeated checks.

Complexity Analysis

Metric	Value
Time	O(n^3 + m \cdot k)
Space	O(n + m \cdot k)

The provided solution has time complexity O(n^3 + m \cdot k), where n is the length of s, m is the number of dictionary words, and k is the average word length. Space complexity is O(n + m \cdot k) due to the DP array and hash or trie storage. The DP iteration over all substrings contributes to the cubic factor, while hash or trie lookups scale linearly with word count and length.

What Interviewers Usually Probe

• Do you recognize the overlapping subproblem structure in this string segmentation scenario?
• Can you optimize substring lookups to avoid repeated dictionary searches using hash sets or tries?
• Will you explain how DP or memoization prevents redundant scanning of overlapping string segments?

Common Pitfalls or Variants

Common pitfalls

• Forgetting that dictionary words can be reused multiple times, leading to false negatives in segmentation.
• Checking all substrings inefficiently without leveraging DP or memoization, causing timeouts.
• Using a list search instead of a hash set, which increases lookup time from O(1) to O(m) per substring.

Follow-up variants

• Word Break II: Return all possible segmentations of s instead of a boolean, exploring recursion with memoization.
• Word Break with Limited Reuse: Each word can be used only a fixed number of times, requiring additional tracking per word.
• Word Break III: Count the number of valid segmentations instead of returning a boolean, focusing on DP sum accumulation.

FAQ

What is the main pattern to solve Word Break efficiently?

The problem relies on array scanning combined with hash lookups to verify dictionary words. DP or memoization prevents redundant substring checks and handles repeated word reuse.

Can I use recursion instead of iterative DP for Word Break?

Yes, recursion with memoization works by caching results for each start index, avoiding redundant computations while still checking all substring splits efficiently.

How does a trie improve Word Break performance?

A trie allows prefix-based early termination, reducing unnecessary substring scans. It works well with DP or memoization to efficiently track valid segmentations with multiple dictionary words.

What common mistakes lead to timeouts in Word Break?

Inefficiently checking all substrings without DP or memoization, repeatedly scanning the wordDict without hash lookups, and ignoring repeated word usage can cause significant slowdowns.

Are there follow-up variants of Word Break to practice?

Yes, including Word Break II to return all segmentations, limited reuse versions where each word has usage limits, and counting valid segmentations instead of boolean output.