Skip to content
BASA DSA

Decode Ways

Medium1-D Dynamic Programming

Each letter from A to Z has a numeric code from 1 to 26. A message is encoded by joining those codes into a string of digits, without separators.

Code
A = 1    B = 2    C = 3
...
X = 24   Y = 25   Z = 26

Given the digit string s, return the number of different ways to decode the entire message. Each group must represent one letter, so its value must be between 1 and 26.

The same string can have several valid groupings. For instance, "121" has three decodings:

  • 1 | 2 | 1 produces "ABA".

  • 12 | 1 produces "LA".

  • 1 | 21 produces "AU".

A code cannot start with zero. The group 10 is valid, but 0 and 01 are not. Every digit must belong to a valid group; if no complete grouping exists, return 0.

The result is guaranteed to fit in a signed 32-bit integer.

Example 1

Input
s = "121"
Output
3

Explanation

Valid splits 1/2/1, 12/1 and 1/21 give three decodings.

Example 2

Input
s = "06"
Output
0

Explanation

Leading zero cannot start a code, and 06 is not a valid two-digit code.

Example 3

Input
s = "2101"
Output
1

Explanation

Only 2/10/1 works; standalone 0 and code 01 are invalid.

Example 4

Input
s = "0"
Output
0

Explanation

Zero alone is invalid because codes start at one.

Constraints

  • 1 <= len(s) <= 100
  • s contains digits
  • The answer fits a signed 32-bit integer

Function contractnumDecodingsArguments: json
Loading draft…
SolutionRuns on your device