iq.lab
Python starts when a code cell comes near or you run one
mediumDynamic programming, 1D target 25 min

Ways to decode

Not solved yetLeetCode 91. Decode Ways

A message of capital letters was turned into digits, with A as 1, B as 2, and so on up to Z as 26, and the codes were written one after another with no gaps. So "LAB" becomes "1212", and so does "ABAB".

You get the digit string s. Count the letter messages that turn into exactly s and return that count. Every code is a number from 1 to 26 written without a leading zero: "8" is H, but "08" is not a code, and neither is "0" on its own. If no message fits, return 0.

Example 1
Inputs = "123"Output3

ABC (1, 2, 3), LC (12, 3) and AW (1, 23).

Example 2
Inputs = "2101"Output1

Only BJA (2, 10, 1). The 0 must join the 1 before it, which leaves the 2 alone, and "01" is not a code.

Example 3
Inputs = "50"Output0

The 0 cannot stand alone, and 50 is bigger than 26.

Constraints

  • 1 ≤ len(s) ≤ 100

  • s holds only the digits 0 to 9, and it may start with 0.

Plan it first

Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.

⌘+Enter runs 0:00Python starts when a code cell comes near or you run one
Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.

Same pattern