leetcode_解码方法(动态规划)
程序员文章站
2022-03-05 10:07:20
...
1、题目描述
包含 A-Z 的字母的消息通过以下规则编码:
'A' -> 1
'B' -> 2
...
'Z' -> 26
给定一个包含数字的编码消息,请确定解码方法的总数。
例如,
给定消息为 "12", 它可以解码为 "AB"(1 2)或 "L"(12)。
"12" 的解码方法为 2 种。
2、题目解析
题目思路不难,重点在于判断条件,除了26这个边界,还有要考虑全面包含0的情况,包括10、101、100、01之类的情况,
用dp[i]代表从0-i的解码方法的个数,也可以从后向前来统计。
3、代码如下
class Solution {
public:
int numDecodings(string s) {//第一遍没有包含“0”这种情况
int i, len = s.length();
if (len == 0||s[0]=='0')return 0;
if (len == 1)return 1;
vector<int> dp(len);
//初始化操作
dp[0] = 1;
if (s[0] > '2'&&s[1]!='0' || (s[0] == '2'&&s[1] > '6') || (s[0] <= '2'&&s[1] == '0')) {//第五遍忘记了等号
dp[1] = 1;
}
else if (s[1] == '0'&&s[0] > '2') {return 0; }
else dp[1] = 2;
for (i = 2; i < len; ++i) {
if (s[i - 1] > '2'&&s[i]!='0' || (s[i - 1] == '2'&&s[i] > '6')||(s[i-1]=='0'&&s[i]!='0')) {//第三遍忘了"101"这种情况;第四遍忘记了s[i]!=0
dp[i] = dp[i - 1];
}
else if (s[i] == '0') {//要考虑等于s[i]==0的情况
if (s[i - 1] > '2'||s[i-1]=='0') {//第二遍没有考虑到0的前一位还是0的情况
return 0;
}
else {
dp[i] = dp[i - 2];
}
}
else {
dp[i] = dp[i - 1] + dp[i - 2];
}
}
return dp[len - 1];
}
};
我的判断情况比较多,代码看着比较乱,下面是别人的代码,非常简洁,看样子是个大神了。。。
class Solution {
public:
int numDecodings(string s) {
if (s.empty())return 0;
vector<int>v(s.size() + 1, 0);
v[0] = 1;
v[1] = (s[0] == '0') ? 0 : 1;
for (int i = 2; i <= s.size(); ++i) {
auto t1 = stoi(s.substr(i - 1, 1));
if (t1>0 && t1<10)v[i] += v[i - 1];
auto t2 = stoi(s.substr(i - 2, 2));
if (t2<27 && t2>9)v[i] += v[i - 2];
}
return v.back();
}
};
继续加油! 上一篇: spring系列10-spring源码分析之事务管理器
下一篇: 使用Rust开发操作系(异常处理)