Decode
ways:
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)
- "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.
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").
Constraints:
- 1 <= s.length <= 100
- s contains only digits and
may contain leading zero(s).
class Solution {
public int numDecodings(String s) {
Integer count = 0;
if (isValid(s.substring(0,1)))
traverse(s.substring(1), count);
if (s.length() >= 2 && isValid(s.substring(0,2)))
traverse(s.substring(2), count);
return count;
}
public boolean traverse(String s, Integer count) {
if (String.isNullOrWhitespace(s)){
count += 1;
return true;
}
if (isValid(s.substring(0,1)))
traverse(s.substring(1), count);
if (s.length() >= 2 && isValid(s.substring(0,2)))
traverse(s.substring(2), count);
return count > 0;
}
public boolean isValid(String s) {
if (s.length() == 1 && s.charAt(0) >= '0' && s.charAt(0) <= '9'){
return true;
}
if (s.length() == 2 &&
(s.charAt(0) > '0' && s.charAt(0) <= '2') &&
((s.charAt(0) == '1' && s.charAt(1) >= '0' && s.chartAt(1) <= '9') ||
(s.charAt(0) == '2' && s.chartAt(1) >= '0' && s.chartAt(1) <= '6')) {
return true;
}
return false;
}
}
