Decode Ways
Problem Description
You have intercepted a secret message encoded as a string of numbers. The message is decoded via the following mapping:
"1" -> 'A'"2" -> 'B'..."25" -> 'Y'"26" -> 'Z'
However, while decoding the message, you realize that there are many different ways you can decode the message because some codes are contained in other codes ("2" and "5" vs "25").
For example, "11106" can be decoded into:
"AAJF"with the grouping(1, 1, 10, 6)"KJF"with the grouping(11, 10, 6)- The grouping
(1, 11, 06)is invalid because"06"is not a valid code (only"6"is valid).
Note: there may be strings that are impossible to decode.Given a string s containing only digits, return the number of ways to decode it. If the entire string cannot be decoded in any valid way, return 0.
The test cases are generated so that the answer fits in a 32-bit integer.
Example 1:
Input: s = "12"
Output: 2
Explanation:
"12" could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: s = "226"
Output: 3
Explanation:
"226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Example 3:
Input: s = "06"
Output: 0
Explanation:
"06" cannot be mapped to "F" because of the leading zero ("6" is different from "06"). In this case, the string is not a valid encoding, so return 0.
Constraints:
1 <= s.length <= 100scontains only digits and may contain leading zero(s).
Solve it on LeetCode
Approaches
1. Recursive Approach
The recursive approach attempts to solve the problem by considering each character individually and tries to decode either one or two characters at a time. This explores all possible combinations leading to a solution.
Intuition:
- If we encounter a single character from '1' to '9', it can be decoded to a letter from 'A' to 'I'.
- A pair of characters from '10' to '26' can be decoded into a letter from 'J' to 'Z'.
- We return 0 if the current character is '0' because it doesn't map to any letter directly.
- For each character, recursively calculate the number of ways to decode the subsequent string.
Code:
- Time Complexity: O(2^N), where (N) is the length of the string due to the branching at each step.
- Space Complexity: O(N) due to the recursion stack.
2. Memoization Approach
The memoization approach is an optimization over the recursive approach where we store the results of subproblems to avoid redundant calculations.
Intuition:
- We use an array to store results of previously computed indices, avoiding recalculations and reducing time complexity.
- Similar recursive structure, but check the memoized results before computing.
Code:
- Time Complexity: O(N), due to storing results and avoiding recomputation.
- Space Complexity: O(N), both for the recursion stack and memoization map.
3. Dynamic Programming Approach
The DP approach builds from the bottom up, filling an array where each position represents the number of ways to decode up to that point.
Intuition:
- Use a
dparray wheredp[i]stores the count of decode ways up to indexi. - Initialize
dp[0]to1as the base case (empty string). - Iterate through the string, filling
dpbased on allowable single and double character decodings.
Code:
- Time Complexity: O(N), iterating through the string once.
- Space Complexity: O(N), for the
dparray.