Decode Ways
A message containing letters from A-Z is being encoded to numbers using the
following 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.
class Solution {
public:
int numDecodings(string s) {
int len = s.length();
if(len == 0){
return 0;
}
int* d = new int[len + 1]; //表示前i个字符有d[i - 1]中解码方式
d[0] = 1; //0个字符的情况通过分析1、2个字符情况得知
if(check(s[0])){
d[1] = 1;
}else{
d[1] = 0;
}
for(int i = 1; i < len; i++){
d[i + 1] = 0;
if(check(s[i-1], s[i])){
d[i+1] += d[i -1];
}
if(check(s[i])){
d[i+1] += d[i];
}
}
int result = d[len];
delete[] d;
return result;
}
private:
bool check(char c){
if(c == '0'){
return false;
}else{
return true;
}
}
bool check(char c1, char c2){
if(c1 == '0' || c1 > '2' || (c1=='2' && c2 > '6' )){
return false;
}else{
return true;
}
}
};原文：http://blog.csdn.net/kangrydotnet/article/details/44701239