Hard

Construct String With Minimum Cost

LAB

Given a target, dictionary words, and costs, return the minimum cost to concatenate words into target, or -1 if impossible.

EXAMPLES

Example 1

Input
{
  "target": "abcdef",
  "words": [
    "ab",
    "abc",
    "cd",
    "def",
    "abcd"
  ],
  "costs": [
    2,
    3,
    1,
    2,
    4
  ]
}

Output
5

FUNCTION SHAPE

target: stringwords: stringArraycosts: intArray→int

SOLUTION NOTE

Similar to word break but with costs. Trie stores minimum cost to form each word. DP finds minimum cost segmentation.

Reveal reference solution +

pythonREFERENCE

def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:
    # Trie with minimum cost at each node
    trie = {}
    for word, cost in zip(words, costs):
        node = trie
        for c in word:
            if c not in node:
                node[c] = {}
            node = node[c]
        node['$'] = min(node.get('$', float('inf')), cost)

    @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]]
            if '$' in node:
                res = min(res, node['$'] + dp(j + 1))

        return res

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

TimeO(n × m)

SpaceO(total word length)

Open on LeetCode ↗