public class Solution {
/
@param s: a string, encoded message
* @return: an integer, the number of ways decoding
*/
public int numDecodings(String s) {
// write your code here
int size = s.size();
if(size == 0)
return 0;
int *dp = new int[size];
dp[0] = 1*(s[0]!='0');
if(size >= 2)
{
string t = s.substr(0,2);
int n = atoi(t.c_str());
dp[1] = dp[0]*(s[1]!='0') + (n>0 && n<=26);
for(int i=2; i<size; i++)
{
string t = s.substr(i-1,2);
int n = atoi(t.c_str());
dp[i] = dp[i-1]*(s[i]!='0') + (n>=10 && n<=26)*dp[i-2];
}
}
return dp[size-1];
}
};