```
/*
define: ways[i] as number of decoding ways for string s[i:]
there are only two cases:
-- initially, at each index i, ways[i] = 0.
-- if s[i : i + 1] is valid, ways[i] += ways[i + 1]; otherwise ways[i] += 0.
-- if s[i : i + 2] is valid, ways[i] += ways[i + 2]; otherwise ways[i] += 0.
*/
public class Solution {
public int numDecodings(String s) {
if (s == null || s.length() == 0) return 0;
int next2 = 1, next1 = 1; // next2 serves as ways[i + 2]; next1 serves as ways[i + 1]
for (int i = s.length() - 1; i >= 0; --i) {
if (next1 == 0 && next2 == 0) return 0; // an obvious shortcut
int oneChar = s.charAt(i) >= '1' && s.charAt(i) <= '9' ? 1 : 0;
int twoChars = i + 1 >= s.length() ? 0 : (s.charAt(i) == '1' && s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '9' ||
s.charAt(i) == '2' && s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '6' ? 1 : 0);
int cur = oneChar * next1 + twoChars * next2;
next2 = next1;
next1 = cur;
}
return next1;
}
}
```