# C++, 5ms, O(n) time and O(1) space, without DP, hashtable, recursive

• ``````class Solution {
public:
// Here is a straightforward method.
// Define res(n) as the total number of ways to decode string(n)
// which is a string of length n. When the next char of string(n)
// can be decoded two times, for example:
//     the next char: 2
//     the last char of string(n): 1
// res(n + 1) will be res(n) + res(n - 1).
// If not, for example:
//     the next char: 8
//     the last char of string(n): 2 ~ 9
// res(n + 1) simply equal res(n).
// Special case:
//     Zero, 0. When the next char of string(n) is 0 and res(n) > res(n - 1),
//     which means two-times decoding occurs at string(n), the
//     two-times decoding has to be reverted.
//     res(n + 1) = res(n - 1)
int numDecodings(string s) {
if (s.length() == 0 || s[0] == '0') {
return 0;
}
int res, pre, ppre;
res = ppre = pre = 1;
for (int i = 1; i < s.length(); i ++) {
if (s[i] == '0') {
if (s[i - 1] != '1' && s[i - 1] != '2') {
return 0;
} else if (pre > ppre) {
res = ppre;
pre = res;
} else {
ppre = pre;
}
} else {
if ((s[i - 1] == '1') || (s[i - 1] == '2' && s[i] <= '6')) {
res = ppre + pre;
ppre = pre;
pre = res;
} else {
ppre = pre;
}
}
}
return res;
}
};``````

• Here is a Java version...

``````public class Solution {
public int numDecodings(String s) {
if(s==null||s.length()==0 || s.charAt(0)=='0'){
return 0;
}
if(s.length()==1){
return 1;
}
int pre=1, ppre=1, res=1;
for(int i=1;i<s.length();i++){
if(s.charAt(i)=='0'){
if(s.charAt(i-1)!='1' && s.charAt(i-1)!='2'){
return 0;
}else if(pre > ppre){
res = ppre;
pre = res;
}else{
ppre = pre;
}
}else{
if(s.charAt(i-1)=='1'||(s.charAt(i-1)=='2'&&s.charAt(i)<='6')){
res = pre + ppre;
ppre = pre;
pre = res;
}else{
ppre = pre;
}
}
}
return res;
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.