How should I practice Minimum-Cost Digit String Decoding?

Start by reading the full statement, solve the visible examples, then compare the pattern against related SquadStack.ai online assessment problems in FastPrep.

Is Minimum-Cost Digit String Decoding associated with SquadStack.ai?

FastPrep tags this as a SquadStack.ai online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Dynamic Programming

Minimum-Cost Digit String Decoding

Learn this problem

● Medium

SquadStack.aiNEW GRADOA

Problem statement

You are given a non-empty digit string digits and an array letterCosts of length 26.

The integers 1 through 26 represent the letters A through Z. The cost of decoding a chunk as letter x is letterCosts[x - 1].

Split digits into valid one- or two-digit chunks. A chunk is valid when:

it has no leading zero, and
its integer value is between 1 and 26, inclusive.

The cost of a decoding is the sum of its decoded-letter costs. Return the minimum cost among all valid decodings. If no valid decoding exists, return -1.

Function

minDecodingCost(digits: String, letterCosts: int[]) → long

Examples

Example 1

digits = "12"letterCosts = [5,6,20,20,20,20,20,20,20,20,20,4,20,20,20,20,20,20,20,20,20,20,20,20,20,20]return = 4

Decoding "12" as A, B costs 5 + 6 = 11. Decoding it as L costs 4, which is smaller.

Example 2

digits = "226"letterCosts = [50,3,50,50,50,8,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,4,50,50,50,10]return = 12

The valid splits are 2|2|6 with cost 14, 22|6 with cost 12, and 2|26 with cost 13. The minimum is 12.

Example 3

digits = "06"letterCosts = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]return = -1

A chunk cannot start with 0, so the string has no valid decoding.

Constraints

1 <= digits.length <= 10^5.
digits contains only the characters '0' through '9'.
letterCosts.length == 26.
0 <= letterCosts[i] <= 10^9.