157. Word Break - Count All Ways

Given a string s and a dictionary of words (space-separated on the second input line, each reusable any number of times), count the number of distinct ways to segment s into a sequence of dictionary words.

Input: The first line contains the string s. The second line contains the dictionary words, space-separated. Output: Print a single integer - the number of distinct ways to segment s into dictionary words.

1 <= |s| <= 200, 1 <= number of dictionary words <= 500

Memoizing purely on the STARTING INDEX (not on the specific path of words used to get there) is what makes this efficient - the count of ways to segment the remaining suffix is always the same regardless of which earlier words were chosen to reach that index.

Count the number of distinct ways a string can be segmented into a sequence of dictionary words. Brute force: Recursively try every dictionary word as a prefix without memoization - this recomputes the SAME 'ways to segment starting from index i' sub-problem repeatedly whenever multiple paths reach the same index, causing exponential blowup for longer strings. Optimised: Memoizing on the STARTING INDEX (since the number of ways to segment a given SUFFIX of the string depends only on that suffix, never on how you got there) ensures each distinct sub-problem is solved exactly once - turning potentially exponential re-exploration into a polynomial-time computation.

Build a dp array from the ground up, where dp[i] represents the number of ways to segment the prefix s[0..i), starting with dp[0] = 1 (empty prefix, one trivial way) and computing each dp[i] by looking back at all valid split points j < i where s[j..i) is a dictionary word (checked via a hash set), adding dp[j] for each such j. This computes exactly the same values as the memoized recursive version but iteratively from the bottom up, avoiding any function call/recursion overhead or risk of stack depth issues, and can be further sped up in practice by only checking substring lengths that actually exist in the dictionary rather than every possible j. Time: O(|s|^2) Space: O(|s|)

Use the same recursive splitting logic as the brute-force approach, but store the computed result (number of ways to segment) for each starting position in a memo array the first time it's computed, and simply return the cached value if that position is ever revisited. Combined with using a hash set for O(1) dictionary lookups, this ensures each of the |s| distinct starting positions is only fully computed once, eliminating the repeated recomputation that made the brute-force version exponential. Time: O(|s|^2) Space: O(|s|)

Recursively try every possible way to split the remaining suffix of the string: at each position, check every possible prefix of the remaining suffix against the dictionary, and for every valid dictionary-word prefix, recurse on the rest of the string, summing up the number of ways found across all valid splits. This correctly counts every distinct segmentation by trying all of them, but because the same suffix of the string can be reached through many different split paths, the same subproblems get recomputed repeatedly, leading to exponential blow-up. Time: O(2^|s|) Space: O(|s|) recursion depth

1. Recursively try every dictionary word as a PREFIX of the remaining string. 2. For each match, recurse on whatever remains AFTER removing that prefix, summing up the number of ways to segment the rest. 3. Memoize on the STARTING INDEX of the remaining substring, so the same remaining-substring sub-problem is never recomputed from scratch.

Time: O(n² ) to O(n² * average word length) with memoization, where n is the string's length - a huge improvement over the exponential unmemoized version. Space: O(n) for the memoization array, plus whatever space the dictionary lookup structure (a hash set) itself requires.

Test a string that can't be segmented at all (0 ways), |s| = 200 with 500 dictionary words for performance, and overlapping short dictionary words that multiply the segmentation count.

Be ready to connect this directly to the yes/no 'Word Break Problem' from the Strings category - this is the exact same recursive structure, just SUMMING counts across all valid prefix matches instead of just checking if ANY valid segmentation exists.