int numDecodings(string s) {
// empty string or leading zero means no way
if (!s.size()  s.front() == '0') return 0;
// r1 and r2 store ways of the last and the last of the last
int r1 = 1, r2 = 1;
for (int i = 1; i < s.size(); i++) {
// zero voids ways of the last because zero cannot be used separately
if (s[i] == '0') r1 = 0;
// possible twodigit letter, so new r1 is sum of both while new r2 is the old r1
if (s[i  1] == '1'  s[i  1] == '2' && s[i] <= '6') {
r1 = r2 + r1;
r2 = r1  r2;
}
// onedigit letter, no new way added
else {
r2 = r1;
}
}
return r1;
}
Concise cpp solution with O(1) space and O(n) time


same idea in Python:
def numDecodings(self, s): if not s or s.startswith('0'): return 0 wo_last, wo_last_two = 1, 1 for i in range(1, len(s)): x = wo_last if s[i] != '0' else 0 y = wo_last_two if int(s[i  1: i + 1]) < 27 and s[i  1] != '0' else 0 wo_last = x + y wo_last_two = x return wo_last