Decode Ways

mediumFREEDynamic ProgrammingBlind 75

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

Output

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 $1$ to $26$ .
Splitting 226: there are three valid ways to cut it:
- $2 \mid 2 \mid 6 \to$ B, B, F, giving 'BBF'
- $22 \mid 6 \to$ V, F, giving 'VF'
- $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 > 26$ anyway).
Output: the count of valid splittings, $1 + 1 + 1 = 3$ . Only the number is returned, not the decoded strings.
Notice: both pairs here, $22$ and $26$ , are $\le 26$ , so each adds a split. For the input "27" the pair $27$ is too big, leaving only 'BG', so the answer is $1$ . A zero can never stand alone and a group like "06" is not a code, so the input "06" has $0$ decodings.

Constraints

1 <= len(s) <= 100
s contains only digits
s does not contain leading zeros except "0" itself

Learn this in

Dynamic Programming BasicsDSA Study Plan

More from Blind 75

Alien Dictionaryhard Clone Graphmedium Combination Summedium Word Search IIhard Merge K Sorted Listshard

Concept primer

Background Knowledge

The "Decode Ways" problem is a classic example of a Dynamic Programming problem. Dynamic Programming is a method for solving complex problems by breaking them down into simpler subproblems, solving each subproblem only once, and storing the solutions to subproblems to avoid redundant computation. In the context of this problem, we need to understand how to break down the string s into smaller subproblems and use the solutions to these subproblems to compute the total number of ways to decode the string.

To approach this problem, we also need to understand the encoding scheme used to map letters to numbers. The scheme is based on the standard ordering of the alphabet, where 'A' corresponds to 1, 'B' corresponds to 2, and so on, up to 'Z' corresponding to 26. This means that a single digit can represent a letter (e.g., '1' -> 'A'), and two digits can also represent a letter (e.g., '11' -> 'AA' or '1' -> 'A' and '1' -> 'A'). We need to consider both cases when decoding the string.

The key to solving this problem lies in recognizing the overlapping subproblems that arise when decoding the string. For example, when decoding the string "12", we need to consider the possibilities for the first digit ('1' -> 'A') and the second digit ('2' -> 'B'), as well as the possibility that the first two digits represent a single letter ('12' -> 'L'). By breaking down the problem into smaller subproblems and solving each subproblem only once, we can efficiently compute the total number of ways to decode the string.

Algorithm/Approach

The general approach to solving this problem is to use a bottom-up dynamic programming strategy. This involves creating a table to store the solutions to subproblems and filling in the table in a systematic way. The table will store the number of ways to decode each prefix of the string s. By using this table, we can avoid redundant computation and efficiently compute the total number of ways to decode the string.

Step-by-Step Strategy

To implement the solution, follow these steps:

Initialize a table dp of size n+1, where n is the length of the string s. The table will store the number of ways to decode each prefix of s.
Set dp = 1, since there is one way to decode an empty string (i.e., do nothing).
For each position i in the string s, consider the possibilities for decoding the prefix s[0..i].
If the current digit s[i] is non-zero, we can decode it separately, so add the number of ways to decode the prefix s[0..i-1] to dp[i].
If the last two digits s[i-1..i] form a valid letter (i.e., between 10 and 26), we can decode them together, so add the number of ways to decode the prefix s[0..i-2] to dp[i].
Finally, return dp[n], which stores the total number of ways to decode the string s.

Common Pitfalls

When implementing the solution, watch out for the following pitfalls:

Forgetting to handle the base case (i.e., dp = 1) correctly.
Failing to consider the possibility that a single digit can represent a letter.
Failing to consider the possibility that two digits can represent a letter.
Not using the table dp to avoid redundant computation.

Time & Space Complexity

The expected time complexity of the solution is $O(n)$ , where $n$ is the length of the string s. This is because we need to iterate over the string once to fill in the table dp. The expected space complexity is also $O(n)$ , since we need to store the table dp of size n+1.

solution.py

Python 3.13

Test results