- 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).
- 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;
}
```