This problem is similar with "climb stairs", but I was stuck in this problem because I didn't fully understand the idea.

The key to this problem is how to choose the strategy for the next move.

Assume S is the string and S1 is a substring of S that we know the number of combinations. Then there are two ways we can move to next step: either append one number or two numbers. That is [S1, XY] or [S1X, Y], where X and Y are new numbers and ',' is the separator. We only need to know if 'Y' itself is valid or a combination of 'XY' is valid. If 'Y' is valid, then the current result should add the answer of [S1X]; if 'XY' is valid, we need to add the answer of [S1].

```
int numDecodings(string s) {
int c1, c2, c3;
c1 = c2 = 1;
c3 = 0;
if (s.size() == 0) return 0;
if (s[0] == '0') return 0;
for (int i = 1; i < s.size(); ++i) {
c3 = 0;
int v = (s[i-1]-'0')*10 + s[i]-'0';
if (v > 9 && v <= 26) //choose [S1,XY], S1 is a substring of S
c3 += c1;
if (s[i] != '0') //choose [S1X, Y] or [S1, X, Y]
c3 += c2;
c1 = c2;
c2 = c3;
}
return c2;
}
```