Problem
A message containing letters from A-Z
can be encoded into numbers using the following mapping:
|
|
To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106"
can be mapped into:
"AAJF"
with the grouping(1 1 10 6)
"KJF"
with the grouping(11 10 6)
Note that the grouping (1 11 06)
is invalid because "06"
cannot be mapped into 'F'
since "6"
is different from "06"
.
Given a string s
containing only digits, return the number of ways to decode it.
The test cases are generated so that the answer fits in a 32-bit integer.
Examples
Example 1:
|
|
Example 2:
|
|
Example 3:
|
|
Expected time complexity is O(n) where n is the number of characters in the given data i.e. encoded string.
Solution
Video explanation
Here is the video explaining below methods in detail. Please check it out:
Method 1 - Recursion
To begin with, we can think of the solution for the easy cases. Suppose string is 1 letter word like: 3
. Then numDecodings
= 1
.
Likewise for the empty string, the numDecodings = 1
as input string would have been ""
as well.
This problem is recursive and can be broken in sub-problems. We start from start of the given digit sequence. We initialize the total count of decodings as 0. We recur for two subproblems.
- If the i-th digit is non-zero, recurse for remaining (i+1) digits and add the result to total count.
- If the first two digits form a valid character (or smaller than 27), recur for remaining (i+2) digits and add the result to total count.
We can also start from the end of the string, following similar logic.
For e.g. for s = 226
, this is how to recursion tree:
graph TD A("226") A --> B("2") A --> C("22") B --> D("2") B --> E("26"):::green C --> F("6"):::green D --> G("6"):::green classDef green fill:#3CB371,stroke:#000,stroke-width:1px,color:#fff;
Code
|
|
|
|
Complexity
- ⏰ Time complexity:
O(2^n)
, as we are making 2 decisions at each point and depth of this tree will be proportional to n. - 🧺 Space complexity:
O(n)
coming from the depth of the recursion.
Dry Run
Here we are going from left to right.
|
|
In the above logic, we have not handled the case when data starts with 0. eg.
|
|
To do so, we can do following:
|
|
Now, handle when we get numWays as negative and return the value accordingly.
The time complexity of above the code is exponential. If we take a closer look at the above program, we can observe that the recursive solution is similar to Generate Nth Fibonacci Number.
Method 2 - Top Down DP with Memoization OR DFS with Cache
Now, let’s see how we can make the process more efficient. When decoding a substring, we notice that there is repetitive work being performed. For example, in the recursion tree for a small string like 226
, the digit 6
is decoded multiple times across different recursive paths.
To optimise this, we can observe that if we are at a certain index in the string, the number of ways to decode the substring from that index to the end will always remain the same, regardless of the path taken to reach that index. This opens up opportunities for memoisation or caching.
Using memoisation, we store the results of previously computed subproblems in a cache (e.g., a dictionary in Python or a HashMap in Java). Whenever a substring starting at a specific index is encountered again, we can simply retrieve the cached result instead of recalculating it.
This optimisation reduces the time complexity to O(n)
because we now process each index in the string only once. The space complexity remains O(n)
due to two factors:
- The recursion stack depth (proportional to the length of the string).
- The memoisation table used to store intermediate results.
Code
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n)
. As, we are now caching the value now, we don’t have to go into 2^n paths. - 🧺 Space complexity:
O(n)
Method 3 - Bottom up DP
We can also solve this problem iteratively using a bottom-up DP approach by solving for smaller substrings first and gradually building up the solution for the full string. This eliminates any recursion overhead.
- Similar to the caching mechanism used in the previous approach, we initialise a DP table, where each entry
dp[i]
represents the number of ways to decode the substrings[0:i]
(i.e., the firsti
characters of the string).
Base Cases
Before filling the DP table, let’s set up the base cases:
dp[0] = 1
: There is one way to decode an empty string — by doing nothing.- For the first character:
- If it’s
'0'
,dp[1] = 0
, as no valid decoding is possible for a single0
. - Otherwise,
dp[1] = 1
because a valid single-digit mapping exists (e.g.,'1' -> A
).
- If it’s
- Remaining
dp
values are initialised to0
.
Filling the DP Table
After setting the base cases, we iterate through the DP table from dp[2]
to dp[n]
(where n = len(s)
) and calculate the result for each position using previously computed results:
- At each position
i
, consider the following two possibilities:- Single-digit decoding:
- If the current character
s[i-1]
is not'0'
, it can be decoded, and we adddp[i-1]
todp[i]
. - This means the current character (e.g.,
"6"
) maps to a valid letter from the previous position.
- If the current character
- Two-digit decoding:
- If the last two characters
s[i-2:i]
form a number between10
and26
, they can be decoded as a valid letter, and we adddp[i-2]
todp[i]
. - This accounts for valid combined mappings (e.g.,
"22" -> V
).
- If the last two characters
- Single-digit decoding:
Code
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n)
- 🧺 Space complexity:
O(n)
Method 4 - Space-optimized Bottom-up DP
If we examine the Bottom-Up DP Approach, we notice that dp[i]
for position i
depends only on the previous two entries: dp[i-1]
(for single-digit decoding) and dp[i-2]
(for two-digit decoding). This means we do not need to maintain the entire DP table. Instead, we can use two variables to store the results of the last two computations (dp[i-1]
and dp[i-2]
).
This recurrence is conceptually similar to the Fibonacci sequence, except that here the summation is conditional and depends on whether the current single-digit or two-digit substring forms a valid mapping.
Here is the logic:
- Use two variables (
prev2
andprev1
) and a temporary variable (current
):prev2
: Representsdp[i-2]
, which is the decoding count for the substring up to two positions prior.prev1
: Representsdp[i-1]
, which is the decoding count for the substring up to the previous position.current
: Temporarily stores the decoding count for the current positioni
.
- Set up the base cases:
- Initialise
prev2 = 1
because there is exactly one way to decode an empty string (doing nothing). - Check if the first character of the string is valid:
- If the first character is not
'0'
, setprev1 = 1
as it can be decoded alone. Otherwise, setprev1 = 0
.
- If the first character is not
- Initialise
- Iterate from index
2
ton
(wheren
is the length of the string), updating the decoding count:- Single-digit decoding:
- If the character
s[i-1]
(current character) is not'0'
, it can be decoded as a letter. - Add
prev1
(the decoding count of the string ending ati-1
) tocurrent
.
- If the character
- Two-digit decoding:
- If the last two characters (
s[i-2:i]
) form a valid number between10
and26
, they can be decoded together. - Add
prev2
(the decoding count of the string ending ati-2
) tocurrent
.
- If the last two characters (
- Single-digit decoding:
- At each iteration, update
prev2
andprev1
:- Move the window forward by setting
prev2 = prev1
andprev1 = current
.
- Move the window forward by setting
- At the end of the loop,
prev1
contains the total decoding ways for the entire string.
Code
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n)
, as we process every character of the string exactly once. - 🧺 Space complexity:
O(1)
, as we no longer store the entire DP table, but only the last two results (prev1
andprev2
).