```
class Solution {
public:
int numDecodings(string s) {
if(s.size()==0 || s[0]=='0')return 0;
int f[3]={0, 1, 1};
for(int i=1; i<s.size(); i++){
f[0]=f[1];f[1]=f[2];
f[2]=f[1]*(s[i]!='0') + f[0]*(s[i-1]!='0' && (s[i-1]-'0')*10+s[i]-'0' <= 26);
}
return f[2];
}
};
```

Assume that we know f(k-1) and f(k), then

case 1:

if the next digit is non-zero and can attach to the k-th digit to forge a legal combination. then f(k+1) = f(k-1)+f(k)

case 2:

if the k+1th digit is zero then it have to attach to the previous digit to forge a legal combination, if it is not legal when attached to the previous digit, then the sequence can't decoded in any way, thus f(k+1)=0 and should return 0, else if it in fact can be attached to the previous digit then f(k+1)=f(k-1)

case 3: if the k+1the digit is non-zero but can't attach to the previous digit, then f(k+1)=f(k)

`f[2]=f[1]*(s[i]!='0') + f[0]*(s[i-1]!='0' && (s[i-1]-'0')*10+s[i]-'0' <= 26);`

in the above code f[2] denotes f(k+1), f[1] denotes f(k) and f[0] denotes f(k-1), s[i]!=0 means that s[i] can be mapped to one of the alphabet, (s[i-1]!='0' && (s[i-1]-'0')*10+s[i]-'0' <= 26) means s[i] can be attached to previous number to form a new number that can have a map to the alphabet.