Given a target and a list of words (reusable), return the fewest words needed to
concatenate into the target, or -1 if it's impossible.
quickestConcat(target, words)
Input format: target | words.
target="purple", words=[purp, p, ur, le, purpl] // → 2 (purp+le)
target="abcdef", words=[ab, abc, cd, def, abcd] // → 2 (abc+def)
target="xyz", words=[a] // → -1
Builds on the buildability check, but now wants the minimum words used. The first word must prefix the remaining target; after removing it, build the rest with as few additional words as possible. So the minimum for a suffix is 1 plus the smallest "minimum for the leftover" over every prefixing word.
An empty suffix needs 0 more words.
Different earlier word choices can leave the same remaining suffix reachable through multiple paths. The naive version recomputes the minimum for that suffix every time, even though — just like buildability — the answer depends only on the suffix itself.
Cache from suffix to minimum word count (or "impossible"). Check before recursing; otherwise, for every prefixing word, recurse on the leftover, take the smallest result across all choices, add 1, cache, return. If nothing matches, the suffix is impossible — propagating to -1 for the original target if unbuildable.
At most n+1 distinct suffixes, each resolved once against every word — roughly O(n²·m) instead of exponential. Once a "can this be done" recursion and a "cheapest way to do this" recursion share the same subproblem structure, memoize both the same way — tracking a number instead of a boolean.
def quickest_concat(target, words):
INF = float("inf")
memo = {}
def best(rest):
if rest == "":
return 0
if rest in memo:
return memo[rest]
m = INF
for w in words:
if w != "" and rest.startswith(w):
sub = best(rest[len(w):])
if sub + 1 < m:
m = sub + 1
memo[rest] = m
return m
r = best(target)
return r if r < INF else -1
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.