题目
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.
解题思路及代码
解码方法数量问题。
英文26个字母相应1到26，给一串数字。问翻译为字母有多少种方法？
这个题第一思路是想到使用组合排列的方法，穷举全部的可能。非常好。写出例如以下代码
class Solution {
public:
int numDecodings(string s) {
int count = 0;
helper(0, s, count);
return count;
}
void helper(int start, const string& s, int& count){
if(start == s.size()){
++count;
return;
}
int key=0;
for(int i=start; i<s.size(); ++i){
if(s[start] == '0') return;
key = 10*key + s[i] - '0' ;
if(key>26) return;
helper(i+1, s, count);
}
}
};
可是提交后出来的结果是超时。
再想想，使用动态规划的方法来做。
对于串s[0...i]的解码数量应该和s[0...i-1], s[0...i-2]的解码数量有关系。
dp[i]: 代表s[0...i-1]的解码数量，
dp[i] = { (s[i-1]!='0')?dp[i-1]:0 } + { s[i-2...i-1]<='26' ? dp[i-2] : 0 } ;
代码例如以下：
class Solution {
public:
int numDecodings(string s) {
int n = s.size();
if( n<=0 || s[0]=='0') return 0;
vector<int> dp(n+1, 0);
dp[1] = dp[0] = 1;
for(int i=2; i<=n; ++i){
if(s[i-1] != '0') dp[i] = dp[i-1];
if(s[i-2]=='1' || (s[i-2]=='2'&&s[i-1]<'7'))
dp[i] += dp[i-2];
}
return dp[n];
}
};
上述动态规划优化后能够仅仅使用3个变量而不是一个数组。代码例如以下：
class Solution {
public:
int numDecodings(string s) {
if(s.size()<=0 || s[0]=='0') return 0;
int cur=0, cur_1 = 1, cur_2 = 1;
for(int i=2; i<=s.size(); ++i){
if(s[i-1] != '0') cur += cur_1;
if(s[i-2]=='1' || (s[i-2]=='2'&&s[i-1]<'7'))
cur += cur_2;
cur_2 = cur_1, cur_1 = cur, cur = 0;
}
return cur_1;
}
};
假设你认为本篇对你有收获，请帮顶。
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvc3dhZ2xl/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast" alt="">
)