Total Number of Ways to Decode a Message
A message containing letters from A to Z is represented using numbers from 1 to 26. Given a digit string s, return the total number of valid ways to decode the entire string.
Encoding
A -> 1B -> 2...Z -> 26
Every digit must belong to a valid one-digit or two-digit encoding. A segment cannot begin with 0, so values such as "0", "06", and "30" cannot be decoded as individual letters.
Method Signature
int numDecodings(String s)
s is the encoded message containing only digit characters.- Return the total number of ways to decode the complete message.
- Return
0 when the message has no valid decoding.
Constraints
1 ≤ s.length() ≤ 100s contains only characters from '0' to '9'.- The answer fits in a signed 32-bit integer.
Examples
Example 1
Method call: numDecodings(s = "123")
Output: 3
Explanation: The valid groupings are 1,2,3, 12,3, and 1,23.
Example 2
Method call: numDecodings(s = "11106")
Output: 2
Explanation: The valid groupings are 1,1,10,6 and 11,10,6.
Example 3
Method call: numDecodings(s = "301")
Output: 0
Explanation: Neither 30 nor a standalone 0 represents a letter, so the complete message cannot be decoded.