Word Break - Count Ways to Segment a String

Given a string S and a dictionary of M distinct words, count the number of distinct ways to split S into a sequence of one or more consecutive substrings such that every substring in the sequence is a word that appears in the dictionary. Two splits are considered different if the set of cut positions differs. Solve this using recursion with memoization over the starting index of the remaining suffix of S.

Input: The first line contains the string S. The second line contains the integer M. Each of the next M lines contains one dictionary word. Output: A single line containing the number of distinct ways to segment S into dictionary words (print it as a 64-bit integer; print 0 if there is no valid segmentation).

1 <= |S| <= 40, 1 <= M <= 50, 1 <= length of each dictionary word <= 20. All strings consist of lowercase English letters.

Using a hash set (not a list) for the dictionary lookup is what keeps each substring check fast - combined with memoization over the starting index, this transforms what looks like an exponential counting problem into a clean, tractable O(|S|²)-ish computation.

Count the number of distinct ways to split a string into a sequence of dictionary words. Brute force: Try every possible way of inserting cut points into the string directly, checking if each resulting piece is a dictionary word - this branches exponentially without memoization, since the SAME starting index gets explored repeatedly via different earlier cut choices. Optimised: Memoizing ways(i) - the number of ways to segment JUST the suffix starting at i - ensures each of the at most |S|+1 distinct starting positions is computed EXACTLY ONCE, no matter how many different earlier segmentation paths lead to it - turning exponential re-exploration into a table with only |S|+1 entries.

1. Define ways(i) = number of ways to segment the SUFFIX S[i..end] using dictionary words; the final answer is ways(0). 2. BASE CASE: ways(|S|) = 1 (the empty remaining suffix has exactly one - the trivial - segmentation). 3. RECURSIVE CASE: ways(i) = sum of ways(j) over every j > i such that S[i..j) is a dictionary word - MEMOIZE ways(i) so each starting index is computed only once.

Time: O(|S|² * average word length) - for each of the |S| starting positions, trying every possible ending position and checking if that substring is a dictionary word. Space: O(|S|), for the memoization array, plus whatever a dictionary lookup structure (like a hash set) requires.

If S cannot be reconstructed from any combination of dictionary words, the answer is 0. If S equals a single dictionary word and no combination of shorter words also reconstructs it, the answer is exactly 1. The recursion must be memoized - without it, highly ambiguous inputs (a dictionary with many short overlapping words) would be exponential and time out.

Be ready to contrast this COUNTING version with the simpler YES/NO 'can this string be segmented at all' version - the counting version needs to SUM contributions from every valid j, not just check if ANY valid j exists.