228. Word Break - Print All Sentences (Trie)

Given a string s and a dictionary of words (space-separated on the second input line, each word reusable any number of times), find every way to segment s into a sequence of dictionary words. Print each valid segmentation as its words separated by single spaces, one segmentation per line, sorted in ascending lexicographic order of the printed sentence. If no segmentation exists, print 'None'. It is guaranteed that at most 200 distinct segmentations exist for the given input.

Input: The first line contains the string s. The second line contains the dictionary words, space-separated (each word reusable any number of times). Output: Print every valid segmentation of s as space-joined words, one per line, sorted lexicographically by the printed sentence; print 'None' if no segmentation exists.

1 <= |s| <= 20, 1 <= number of dictionary words <= 50

Sorting the final list of complete sentences AFTER collecting them (rather than relying on the trie's or recursion's natural traversal order) is what guarantees the required lexicographic output order, regardless of dictionary input order or trie child ordering.

Given a squished-together string of letters and a dictionary of real words, find every possible way to insert spaces so the whole thing reads as a sequence of real dictionary words. Brute force: At each position, try matching EVERY dictionary word individually against the string starting there (not using a trie at all) - this works, but for each position you re-scan the entire dictionary word list separately, doing redundant character comparisons across dictionary words that share common prefixes. Optimised: Building a trie of the dictionary up front lets a SINGLE walk starting at any string position discover ALL dictionary words that start there simultaneously (since shared prefixes across dictionary words are only walked once, not once per word) - collecting every word-end flag encountered along that one walk, rather than separately checking each dictionary word one at a time against the same starting position.

Insert every dictionary word into a Trie, then during backtracking walk the Trie character by character alongside the current position in s instead of hashing and looking up whole substrings; the moment the path falls off the Trie (no dictionary word shares that prefix), stop extending immediately rather than testing longer substrings that could never match. Combined with the same suffix-feasibility DP for pruning, this shares common prefixes among dictionary words and avoids repeatedly hashing/comparing substrings character-by-character from scratch, reducing the constant-factor cost of exploring each candidate word. Time: O(n^2 + n*numWords + output size) Space: O(n^2 + total dictionary characters)

First run a bottom-up DP over s (O(n^2) with the dictionary in a hash set) that marks, for every starting index, whether the remaining suffix can be segmented into dictionary words at all. Then run the same backtracking as before, but before recursing into a suffix, check the DP table and immediately abandon any branch whose suffix is marked unsegmentable. This prunes away entire dead subtrees of the recursion before they're explored, so time is no longer wasted rediscovering that the same infeasible suffix fails again and again. Time: O(n^2 + output size) Space: O(n^2)

Recursively try every possible split point of the remaining suffix of s: for each prefix, check if it is a dictionary word using a hash set, and if so recurse on the rest of the string, backtracking to build up the full sentence whenever the recursion reaches the end of s. Because failing suffixes (portions of s that can never be fully segmented) get re-explored from scratch every time a different earlier choice leads back to them, a lot of duplicate work is repeated across branches. Time: O(2^|s|) Space: O(|s|)

1. Build a trie from every word in the dictionary up front. 2. Starting from position 0 in the string, walk the trie one character at a time along the string's remaining characters. 3. Every time your walk passes through a node marked 'end of word', that's a valid dictionary word ending at this exact position - recursively try continuing the segmentation from right after it. 4. Collect every full segmentation that successfully reaches the very end of the string, then sort all the found sentences alphabetically before printing.

Time: In the worst case, still exponential in the number of valid segmentations (since the problem asks you to print potentially many complete sentences), but the trie meaningfully speeds up the per-position word-matching step compared to re-checking every dictionary word individually at every position. Space: Proportional to the total characters across all dictionary words (for the trie), plus space for all the recursive segmentations being built and eventually collected.

Test a string with no valid segmentation ('None'), a string with exactly one valid segmentation, and a segmentation that reuses the same dictionary word more than once.

Be ready to explain the specific advantage a trie provides here over a plain hash set of dictionary words: at any given string position, a trie walk discovers ALL matching dictionary words starting there in ONE pass, rather than checking membership word-by-word.