28
03/2015
[LeetCode] Decode Ways
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.
解题思路：
动态规划。这种题目分两种情况讨论。若最后一个字符与前一个字符联合编码(且符合条件)，则d[i]+=d[i-2]。若最后一个字符单独编码（且符合条件），则d[i] += d[i-1]。发现自己动态规划很不熟悉，分析问题的亟待提高啊。
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;
}
}
};转载请注明：康瑞部落 » [LeetCode] Decode Ways
0 条评论