Given a target string and a list of words, return true if the target can be built
by concatenating words from the list, reusing words as many times as needed.
canConcat(target, words)
Input format: target | words. An empty target is always constructible.
target="abcdef", words=[ab, abc, cd, def, abcd] // → true (abc+def)
target="skateboard", words=[bo, rd, ate, t, ska, sk, boar] // → false
target="", words=[a] // → true
The first word used must be one of the given words and must match a prefix of the target exactly. Once committed, the rest is the same problem, smaller: can the remaining suffix also be built from the same word list? So the target is buildable if some word in the list prefixes the current remaining string, and the suffix left after removing it is itself buildable.
An empty remaining string needs no more words — trivially buildable.
Different choices of earlier words can leave the same remaining suffix — a short word then a longer one, versus a different combination, might strip the same total prefix. The naive recursion re-explores that same suffix every time, even though the answer never depends on which earlier words got you there. This can blow up exponentially for longer targets.
Whether a suffix can be built depends only on that suffix and the fixed word list — never on which words stripped away the earlier part. Cache from suffix to true/false. Check before exploring; otherwise try every word that prefixes the suffix, recurse on the leftover, and return true the moment one succeeds; false if none do.
At most n+1 distinct suffixes for a target of length n, each resolved once. Checking one suffix against every word (itself proportional to word length) gives roughly O(n²·m) for m words — far better than unmemoized exponential blowup. "Strip a valid prefix, recurse on the suffix, cache by suffix" is the backbone of the word-break family.
def can_concat(target, words):
memo = {}
def build(rest):
if rest == "":
return True
if rest in memo:
return memo[rest]
for w in words:
if w != "" and rest.startswith(w) and build(rest[len(w):]):
memo[rest] = True
return True
memo[rest] = False
return False
return build(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.