Yesterday, Bro Luo told me: "Why don't you improve your English by writing your blogs in English?" I think it may be a good way and i did so today.

Problem Description:

```
A message containing letters from A - Z is being encoded to numbers using the follow mapping:
```

'A' -> 1

'B' -> 2

...

'Z' -> 26

```
Given an encoded message containing digits, determine the total number of ways to decode it.
```

For example,

Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

My Solution:

```
I used dynamic programming to solve it. For each char in string s can be divided in four types.
```

1.Only can be combined with pre-one

thus dp[i] = dp[i - 2], cause the pre one(i - 1) must combine with i

2.Only can be self alone

thus dp[i] = dp[i - 1]

- Both can

thus dp[i] = dp[i - 1] + dp[i - 2]

4 Both can NOT:

thus return 0, cause the message can be decode

```
Of course, return dp[len - 1] if not return before.
class Solution {
```

public:

bool canCombine(char a, char b)

{

if(a >= '3') return false;

if(a == '2'){

if(b <= '6') return true;

else return false;

}

if(a == '0') return false;

return true;

}

```
bool canAlone(char a)
{
if(a >= '1' && a <= '9') return true;
return false;
}
int numDecodings(string s) {
if(s == "") return 0;
if(s[0] == '0') return 0;
if(s.length() < 2) return 1;
int dp[50000];
dp[0] = 1;
bool canComb = canCombine(s[0],s[1]);
bool canAlon = canAlone(s[1]);
if(canComb && canAlon)
dp[1] = dp[0] + 1;
else if(!canComb && !canAlon)
return 0;
else
dp[1] = dp[0];
for(int i = 2; i < s.length(); i ++){
bool canComb = canCombine(s[i - 1], s[i]);
bool canAlon = canAlone(s[i]);
if(canComb && canAlon){
dp[i] = dp[i - 1] + dp[i - 2];
}else if(canComb){
dp[i] = dp[i - 2];
}else if(canAlon){
dp[i] = dp[i - 1];
}else{
dp[i] = 0;
return 0;
}
}
return dp[s.length() - 1];
}
```

};