61. Word Break Problem

Given a string s and a dictionary of words (space-separated on the second input line), print 'Yes' if s can be segmented into a sequence of one or more dictionary words (words may be reused any number of times), otherwise print 'No'.

Input: The first line contains the string s. The second line contains the dictionary words, space-separated. Output: Print 'Yes' if s can be segmented into dictionary words, otherwise print 'No'.

1 <= |s| <= 300, 1 <= number of dictionary words <= 1000

Using a hash set (not a list) for the dictionary is what keeps each substring-lookup at O(1) (average case) rather than O(dictionary size) - a small but important implementation detail for meeting the stated constraints efficiently.

Check whether a string can be fully broken up into a sequence of words that all appear in a given dictionary, reusing dictionary words as many times as needed. Brute force: Try every possible way of splitting the string into pieces recursively, checking if each piece is a dictionary word - this branches exponentially without memoization, since the same starting position gets re-explored repeatedly across different split choices. Optimised: The DP array dp[i] captures exactly the reusable sub-question 'can the string UP TO position i be broken correctly' - computing it once per position (rather than re-deriving it every time a recursive branch reaches that position) turns exponential recursion into a table with only (string length + 1) entries.

Build a boolean array dp where dp[i] means the prefix s[0..i) can be segmented, with dp[0] = true as the base case. Fill it left to right; for each i, instead of testing every possible split point j < i, only test the split points corresponding to the actual lengths of words present in the dictionary (precomputed once into a small set of lengths) - since a valid last word must have one of those lengths. This keeps the same worst-case quadratic bound but does dramatically less work in practice whenever the dictionary's word lengths are limited, and avoids recursion entirely, removing call-stack overhead for the maximum string length of 300. Time: O(n^2) worst case, typically much faster Space: O(n + total dictionary characters)

Try every possible first-word split: for each prefix of s that appears in the dictionary, recursively check whether the remaining suffix can itself be segmented into dictionary words, returning true as soon as any split works. This directly mirrors the definition of a valid segmentation, but the same suffix can be reached through many different earlier choices and gets re-explored from scratch every time, giving an exponential number of recursive calls in the worst case. Time: O(2^n) Space: O(n) for the recursion stack

Store the dictionary words in a hash set for O(1) average lookup, and cache the result of 'can the suffix starting at index i be segmented' the first time it's computed, so later calls for the same index return instantly instead of re-branching. Since there are only n distinct starting indices, and each one tries at most n possible split points, the total work collapses from exponential to quadratic - the logic is identical to the brute force, it just never solves the same subproblem twice. Time: O(n^2) Space: O(n)

1. Build a boolean array dp where dp[i] means 'can the first i characters of the string be fully broken into dictionary words'. 2. dp[0] is true (an empty prefix is trivially breakable). 3. For each position i, check every earlier position j: if dp[j] is true AND the substring from j to i is a valid dictionary word, then dp[i] is also true. 4. The final answer is dp[length of the whole string].

Time: O(n² ) to O(n² * average word length), where n is the string's length - for each position i, you check every earlier position j and verify a substring against the dictionary. Space: O(n) for the DP array, plus whatever space the dictionary lookup structure (like a hash set) itself requires.

s exactly equal to one dictionary word; a dictionary word that must be reused multiple times to build s; s that cannot be segmented at all; s up to length 300 and up to 1000 dictionary words for performance.

Be ready to extend this to 'Word Break II' (printing every valid segmentation, not just yes/no) as a common, harder follow-up - it uses the same DP idea but also reconstructs and collects the actual segmentations.