#3213

Construct String with Minimum Cost

hard · 19% accepted · 172 likes · top 1%

array · string · dynamic programming · suffix array

⊣ practice⊣ open on leetcode ↗

Description

You are given a string target, an array of strings words, and an integer array costs, both arrays of the same length.

Imagine an empty string s.

You can perform the following operation any number of times (including zero):

- Choose an index i in the range [0, words.length - 1].

- Append words[i] to s.

- The cost of operation is costs[i].

Return the minimum cost to make s equal to target. If it's not possible, return -1.

Solution