Cheapest Build From Pieces

Hard

You need to type out the string phrase by appending ready-made pieces to an initially empty string. Piece pieces[i] costs prices[i], and every piece may be used any number of times (or not at all). Pieces can only be added at the end of what is already typed. Return the smallest total cost that produces exactly phrase. If phrase cannot be built, return -1.

Example 1

phrase='moonlight', pieces=['moon', 'light', 'moonl', 'ight', 'mo', 'on'], prices=[8, 5, 3, 4, 2, 2] → 7

moonl + ight costs 3 + 4 = 7. The option mo + on + light costs 9, and moon + light costs 13.

Example 2

phrase='abab', pieces=['ab', 'b', 'aba'], prices=[3, 1, 1] → 2

Both ab + ab (6) and aba + b (2) work; take the cheaper one. A piece may be used more than once.

Example 3

phrase='xyz', pieces=['xy', 'yz'], prices=[1, 1] → -1

Constraints

1 ≤ len(phrase) ≤ 5·10⁴
1 ≤ len(pieces) = len(prices) ≤ 5·10⁴
1 ≤ len(pieces[i]) ≤ len(phrase)
The total length of all pieces is at most 5·10⁴
phrase and the pieces consist of lowercase English letters
1 ≤ prices[i] ≤ 10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array String Dynamic Programming Suffix Array

Similar problems

Every Way to Space the Words Hard Words Built From Shorter Words Hard Numbers From Working Keys Hard Assembling Fragments Hard Cut Columns to Sort Every Row Hard

Input

phrase='moonlight', pieces=['moon', 'light', 'moonl', 'ight', 'mo', 'on'], prices=[8, 5, 3, 4, 2, 2]

Expected

Run checks the first 3 tests in your browser. Submit checks all 125 tests on the server, hidden ones included.