Given a target and a list of words (reusable), return the number of ways to
build the target by concatenating words. Different orderings of words count as
different ways.
countCompounds(target, words)
Input format: target | words. An empty target has exactly one way (use nothing).
target="purple", words=[purp, p, ur, le, purpl] // → 2
target="abcdef", words=[ab, abc, cd, def, abcd, ef] // → 3
target="xyz", words=[a] // → 0
Extends buildability once more: count every valid way to assemble the target, where different orderings count as distinct. The first word must prefix the remaining target; after removing it, the rest must be assembled from what's left. Since a word choice plus everything after it is one complete way, the total ways for a suffix is the sum, over every prefixing word, of the ways to build what's left — an accumulation across every valid first choice, not a max or a single check.
An empty suffix has exactly one way: use no more words. This lets a completed construction contribute exactly 1 to whichever branch just finished.
Words reuse freely, so the ways to complete a suffix depend only on that suffix, never on which words stripped away the earlier part. A direct implementation reaches the same suffix through many different earlier combinations, recomputing its full count every time even though the value is identical — redundant recomputation (not double-counting, since summing independent branches is correct), growing exponentially with target length.
The subproblem is the remaining suffix. Cache from suffix to ways-to-build-it. Check before summing; otherwise sum "ways for the suffix after removing this word" over every prefixing word, cache the total, return it.
At most n+1 distinct suffixes, each computed once against every word — roughly O(n²·m). The pattern generalizes cleanly: swap "does any choice work" (OR) for "how many ways across all choices" (sum), while the subproblem and memoization strategy stay the same.
def count_compounds(target, words):
memo = {}
def ways(rest):
if rest == "":
return 1
if rest in memo:
return memo[rest]
total = 0
for w in words:
if w != "" and rest.startswith(w):
total += ways(rest[len(w):])
memo[rest] = total
return total
return ways(target)
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.