goal starting from an empty one. There is a set of pieces pieces with prices prices: for prices[i] you may append pieces[i] to the end of the current string. Each piece can be used any number of times, or not at all.
Return the minimum total price that produces exactly goal. If goal cannot be built, return -1.goal="banana", pieces=["ban", "ana", "b", "an", "banana"], prices=[4, 3, 1, 2, 20] → 6
"b" + "an" + "an" leaves a single "a" that no piece covers. "b" + "an" + "ana" costs 1 + 2 + 3 = 6, while "ban" + "ana" costs 4 + 3 = 7. The answer is 6.
goal="door", pieces=["do", "or", "oo"], prices=[1, 1, 1] → 2
"do" followed by "or" gives "door" for 2. The piece "oo" does not help: it fits neither the start nor the end.
goal="cat", pieces=["ca", "at"], prices=[5, 5] → -1
Pieces can only be appended, never overlapped. "ca" + "at" gives "caat", not "cat", so the answer is -1.
goal and every pieces[i] consist of lowercase English lettersgoal="banana", pieces=["ban", "ana", "b", "an", "banana"], prices=[4, 3, 1, 2, 20]
6
Run checks the first 3 tests in your browser. Submit checks all 125 tests on the server, hidden ones included.