This solution is almost the same as the normal one which costs O(n) space. But the length of integer array can be reduced from n+1 to 2 by mod 2(&1 in deed).

```
public class Solution {
public int numDecodings(final String s) {
if (s.isEmpty()) {
return 0;
}
// count[start & 1] is the decode ways of s.substring(start)
final int[] count = new int[2];
count[(s.length() - 1) & 1] = s.charAt(s.length() - 1) > '0' ? 1 : 0;
count[(s.length() & 1)] = 1;
for (int start = s.length() - 2; start >= 0; start--) {
if (s.charAt(start) > '0') {
if (s.charAt(start) == '1' || (s.charAt(start) == '2' && s.charAt(start + 1) < '7')) {
count[start & 1] += count[(start + 1) & 1];
} else {
count[start & 1] = count[(start + 1) & 1];
}
} else {
count[start & 1] = 0;
}
}
return count[0];
}
}
```