# My easily understanding solution and explanation to it!

• 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]

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];
}
``````

};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.