Medium

Minimum Number of Valid Strings to Form Target I

LAB

Return the minimum number of dictionary words needed to concatenate into target, or -1 if impossible.

EXAMPLES

Example 1

Input
{
  "words": [
    "abc",
    "aaaaa",
    "bcdef"
  ],
  "target": "aabcdabc"
}

Output
3

FUNCTION SHAPE

words: stringArraytarget: string→int

SOLUTION NOTE

Build trie of all word prefixes. DP tries all valid prefixes at each position, taking minimum count.

Reveal reference solution +

pythonREFERENCE

def minValidStrings(self, words: List[str], target: str) -> int:
    # Build trie of all prefixes
    trie = {}
    for word in words:
        node = trie
        for c in word:
            if c not in node:
                node[c] = {}
            node = node[c]

    @cache
    def dp(i):
        if i == len(target):
            return 0

        node = trie
        res = float('inf')
        for j in range(i, len(target)):
            if target[j] not in node:
                break
            node = node[target[j]]
            res = min(res, 1 + dp(j + 1))

        return res

    ans = dp(0)
    return ans if ans != float('inf') else -1

TimeO(n × m)

SpaceO(total prefix length)

Open on LeetCode ↗