Problem Statement
Secret Message Decoder
You're a cryptographer working for a secret agency. You've intercepted an encoded message that uses a simple substitution cipher where letters are represented by numbers:
'A' -> '1''B' -> '2'...'Z' -> '26'
The message is a string containing only digits. Your task is to determine the total number of possible ways to decode this message.
For example, the message "12" could be decoded as "AB" (1 2) or "L" (12). So there are 2 possible ways to decode it.
Note that a valid decoding must map to a letter, so numbers like "00", "30", or "99" are invalid because there's no letter corresponding to them.
Examples
Example 1:
Input: s = "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: s = "226"
Output: 3
Explanation: It 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 any letter. A valid encoding starts with a non-zero digit.
Constraints
- 1 <= s.length <= 100
- s contains only digits and may contain leading zero(s)
- The answer is guaranteed to fit in a 32-bit integer
Problem Breakdown
To solve this problem, we need to:
- A digit can be decoded on its own if it's not '0'
- Two consecutive digits can be decoded together if they form a number between 10 and 26
- Leading zeros make a digit invalid for decoding (e.g., '06' cannot be decoded as 'F')
- This problem has optimal substructure, making it suitable for dynamic programming
- The number of ways to decode a string depends on the number of ways to decode its prefixes
String Problems
Learning Objective
Apply string manipulation concepts to solve a real-world problem.
Secret Message Decoder
You're a cryptographer working for a secret agency. You've intercepted an encoded message that uses a simple substitution cipher where letters are represented by numbers:
'A' -> '1''B' -> '2'...'Z' -> '26'
The message is a string containing only digits. Your task is to determine the total number of possible ways to decode this message.
For example, the message "12" could be decoded as "AB" (1 2) or "L" (12). So there are 2 possible ways to decode it.
Note that a valid decoding must map to a letter, so numbers like "00", "30", or "99" are invalid because there's no letter corresponding to them.
Examples
Example 1:
It could be decoded as "AB" (1 2) or "L" (12).
Example 2:
It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Example 3:
"06" cannot be mapped to any letter. A valid encoding starts with a non-zero digit.
Problem Breakdown
Constraints:
- 1 <= s.length <= 100
- s contains only digits and may contain leading zero(s)
- The answer is guaranteed to fit in a 32-bit integer
Key Insights:
A digit can be decoded on its own if it's not '0'
Two consecutive digits can be decoded together if they form a number between 10 and 26
Leading zeros make a digit invalid for decoding (e.g., '06' cannot be decoded as 'F')
This problem has optimal substructure, making it suitable for dynamic programming
The number of ways to decode a string depends on the number of ways to decode its prefixes
Real-World Application
This problem has several practical applications:
Cryptography
Analyzing the number of possible interpretations for encoded messages in cryptographic systems.
Natural Language Processing
Determining possible word segmentations in languages without clear word boundaries.
Communication Systems
Analyzing ambiguity in message transmission and developing error correction codes.