欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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();
	}
};
继续加油!