Decode Ways
Problem Statement
A message containing letters from A-Z can be encoded into numbers using the following mapping: 'A' -> "1", 'B' -> "2", ..., 'Z' -> "26". 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), or "KJF" with the grouping (11 10 6). Given a string s containing only digits, return the number of ways to decode it.
Constraints:
- 1 <= s.length <= 100
- s contains only digits and may contain leading zero(s)
Input Format:
- A string s containing only digits
Output Format:
- Return the number of ways to decode s
Examples:
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").
Solutions
Dynamic Programming
Use a bottom-up dynamic programming approach to build the solution by calculating the number of ways to decode each prefix of the string.
Space-Optimized Dynamic Programming
Optimize the space complexity by only storing the last two results, since we only need dp[i-1] and dp[i-2] to calculate dp[i].
Recursive Approach with Memoization
Use recursion with memoization to solve the problem top-down, calculating the number of ways to decode from each position.
Algorithm Walkthrough
Example input: nums = []
Step-by-step execution:
- Initialize dp array: dp = [1, 1, ?, ?]
- i=2: dp[2] = dp[1] (single '2') + dp[0] (two-digit '22') = 1 + 1 = 2
- i=3: dp[3] = dp[2] (single '6') + dp[1] (two-digit '26') = 2 + 1 = 3
- Return dp[3] = 3
Hints
Hint 1
Hint 2
Hint 3
Video Tutorial
Video tutorials can be a great way to understand algorithms visually
Visualization
Visualize how the dynamic programming table is filled, showing the number of ways to decode each prefix of the string.
Key visualization elements:
- current position
- one-digit decode
- two-digit decode
Implementation Notes
This problem is a classic example of dynamic programming where the number of ways at each position depends on previous results. The key insight is recognizing the decision points at each character: either decode it alone or combine it with the previous character.