Given a target and a list of parts, return true if the target can be formed by
concatenating parts where each part is used at most once (no reuse). Order of
concatenation is up to you, but each listed part may be consumed only one time.
validCompound(target, parts)
Input format: target | parts. An empty target is always valid.
target="sunflower", parts=[sun, flower, sun] // → true
target="aa", parts=[a] // → false (only one 'a' available)
target="aa", parts=[a, a] // → true
This looks like word-break, but each part can be used at most once. In the reusable-word versions, the remaining suffix was all the state needed, since nothing about which words were already used mattered. Here, whether a part is still available depends on the full history of what's already been spent — not just how much of the target remains.
At each step, try every unused part that prefixes the remaining target. Using one means marking it consumed and recursing on the suffix left, with the updated used-set. The target is buildable if any choice eventually leads to a fully matched remaining string.
An empty remaining target means success, regardless of which parts remain unused.
Since reuse is forbidden, "can the rest be built from here" depends on both position in the target and which parts remain available. Two paths reaching the same position with different consumed sets face different futures — position alone no longer identifies the subproblem.
Represent "which parts remain" as a bitmask, one bit per part. The subproblem is the pair (position, bitmask). Memoizing on this pair means any two paths that consumed the same set of parts and reached the same position are recognized as identical, solved once, regardless of the order parts were used in.
Without caching, the recursion re-derives the answer for the same (position, mask) combination every time a different part ordering arrives there — and the number of orderings grows exponentially. But the number of distinct (position, mask) pairs is bounded by target length × 2^(parts), since a mask over k parts has only 2^k values. Memoizing caps the work at roughly O(n · 2ⁿ). When a resource can only be used once, position alone often stops being enough state — fold "what's already consumed" into the subproblem identity, typically via a bitmask for a small resource pool.
def valid_compound(target, parts):
memo = {}
def build(pos, mask):
if pos == len(target):
return True
key = (pos, mask)
if key in memo:
return memo[key]
for i in range(len(parts)):
p = parts[i]
if (mask & (1 << i)) != 0 or p == "":
continue
if target.startswith(p, pos) and build(pos + len(p), mask | (1 << i)):
memo[key] = True
return True
memo[key] = False
return False
return build(0, 0)
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.