int numDecodings(string s) {
if (!s.size()  s.front() == '0') return 0;
// r2: decode ways of s[i2] , r1: decode ways of s[i1]
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;
}
A concise dp solution


if (s[i] == '0') r1 = 0;
I tried your code under test case s = "201", the correct answer should be one, but I got zero.
I think if you wanna avoid these complicated '0' cases, the only way is to visit the string from back to end, like the code below.
Otherwise, you need to consider two kinds of cases, one is like "120" which is valid, and the other one is "130" which returns zero immediately.
int numDecodings(string s) { int len = s.size(); if(!len) return 0; vector<int> memo(len+1, 0); memo[len] = 1; memo[len1] = s[len1] == '0' ? 0 : 1; for (int i = len2; i >= 0; i) { if(s[i] == '0') continue; else{ if(stoi(s.substr(i,2))<=26) memo[i] = memo[i+1]+memo[i+2]; else memo[i] = memo[i+1]; } } return memo[0]; }

We thought exactly the same way~~ lol
public class Solution { public int numDecodings(String s) { if (s.length() == 0) return 0; int dpn_2 = 1; int dpn_1 = 0; if(s.charAt(0)=='0') return 0; else dpn_1 =1; for(int i=1;i int dpn=0; if(s.charAt(i)=='0'){ dpn_1=0; } dpn=(Integer.parseInt(s.substring(i1,i+1))<=26)?dpn_1+dpn_2:dpn_1; dpn_2=dpn_1; dpn_1=dpn; } return dpn_1; } }

// r2: decode ways of s[i2] , r1: decode ways of s[i1]
int r1 = 1, r2 = 1;I have a question for the initial value r1 and r2, why both of them are assigned to 1? I am curious the meanings behind this initial value. I can understand the first entry into for loop is i==1, so r1 is the way of decoding for s[0], and it is not '0', so the initial value should be 1. How to explain the r2 which is s[1]? Anyone? Thanks.