v9.1.1
Menu

Decode Ways

mediumPRODynamic ProgrammingGoogle DSA

A message containing letters A-Z can be encoded as numbers: 'A' -> "1", 'B' -> "2", ..., 'Z' -> "26".

Given a string s containing only digits, return the number of ways to decode it.

To decode, split s into groups of one or two digits where every group maps to a letter. A group with a leading zero (such as "06") is not a valid code, and "0" on its own maps to nothing. If no valid decoding exists, return 0.

Example

Input
226
Output
3
Reasoning
  • Input: s is a string of digits, here 226. A decoding splits it into consecutive groups of one or two digits, and every group must be a code from 11 to 2626.
  • Splitting 226: there are three valid ways to cut it:
    • 2∣2∣6→2 \mid 2 \mid 6 \to B, B, F, giving 'BBF'
    • 22∣6→22 \mid 6 \to V, F, giving 'VF'
    • 2∣26→2 \mid 26 \to B, Z, giving 'BZ'
  • Ruled out: reading all three digits as one group is not allowed, since a code has at most two digits (and 226>26226 > 26 anyway).
  • Output: the count of valid splittings, 1+1+1=31 + 1 + 1 = 3. Only the number is returned, not the decoded strings.
  • Notice: both pairs here, 2222 and 2626, are ≤26\le 26, so each adds a split. For the input "27" the pair 2727 is too big, leaving only 'BG', so the answer is 11. A zero can never stand alone and a group like "06" is not a code, so the input "06" has 00 decodings.

Constraints

  • 1 <= len(s) <= 100
  • s contains only digits and may contain leading zeros

More from Google DSA

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Test results

Sign in to run your code against the test cases.