# 1ms java clean solution with explanation

1. numbers that starts with 1,2 may have two ways of decoding. Decode by single '1'('2') or decode with the following number togeter, Therefore, if current element is i, f(i) = f(i + 1) + f(i + 2)(note that the second part may not exist when the ith elememnt is 2 and the (i + 1)th element is greater than 6).
2. numbers that starts with 0 cannot be decoded.

``````public int numDecodings(String s) {
int n = s.length();
char[] c = s.toCharArray();
if ((n == 0) || (c[0] == '0')) return 0;
if (n == 1) return 1;
int f2 = c[n - 1] == '0' ? 0 : 1; // f(i + 2), start from c[n - 1]
int f1 = c[n - 2] == '0' ? 0 : f2; // f(i + 1), start from c[n - 2]
if ((c[n - 2] == '1') || ((c[n - 2] == '2') && (c[n - 1] < '7'))) f1++;
for (int i = n - 3; i >= 0; i--){
if (c[i] == '0'){
if ((c[i - 1] != '1') && (c[i - 1] != '2')) return 0; //unable to decode 0
else {
i--;
f2 = 0; //f1 maintains the same
continue;
}
}
if ((c[i] != '1') && ((c[i] != '2') || (c[i + 1] > '6'))) f2 = f1; //f1 maintains the same
else {
int t = f1;
f1 = f1 + f2;
f2 = t;
}
}
return f1;
}``````

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