【LeetCode每日一题】91. 解码方法
【LeetCode每日一题】91. 解码方法
公众号guangcity
发布于 2021-05-08 15:31:20
发布于 2021-05-08 15:31:20
文章被收录于专栏：光城(guangcity)
1.题目
一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
'A' -> 1 'B' -> 2 ... 'Z' -> 26 要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：
"AAJF" ，将消息分组为 (1 1 10 6) "KJF" ，将消息分组为 (11 10 6)
示例 1：
输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
示例 2：
输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
2.题解
递归
超时，卡在用例：
"111111111111111111111111111111111111111111111"
选择与不选择两种。
class Solution {
public:
map<int, char> m;
int count = 0;
int numDecodings(string s) {
for (int i = 1; i <= 26; i++) {
m[i] = 'A' + (i - 1);
}
dfs(s, 0, s.size());
return count;
}
void dfs(string& s, int start, int end) {
if (start > end) return;
if (start == end) {
count++;
return;
}
// 排除start不存在情况
if (!m.count(s[start]-'0')) { // '0'
return;
}
// 选择i
dfs(s, start + 1, end);
if (start + 1 < end) {
int tmp = (s[start] - '0') * 10 + s[start + 1] - '0';
// 选择start与start+1
if (m.count(tmp)) {
dfs(s, start + 2, end);
}
}
return;
}
};
记忆化搜索优化
将走过的记录记录在map中。
class Solution {
public:
map<int, char> m;
map<pair<int,int>, int> memo;
int numDecodings(string s) {
for (int i = 1; i <= 26; i++) {
m[i] = 'A' + (i - 1);
}
int count = dfs(s, 0, s.size());
return count;
}
int dfs(string& s, int start, int end) {
auto x = make_pair(start, end);
if (memo.count(x)) return memo[x];
if (start > end) return memo[x] = 0;
if (start == end) {
return memo[x] = 1;
}
// 排除start不存在情况
if (!m.count(s[start]-'0')) { // '0'
return memo[x] = 0;
}
// 选择i
int count = dfs(s, start + 1, end);
if (start + 1 < end) {
int tmp = (s[start] - '0') * 10 + (s[start + 1] - '0');
// 选择start与start+1
if (m.count(tmp)) {
count += dfs(s, start + 2, end);
}
}
return memo[x] = count;
}
};
动规
dp[i]表示字符串以i为结尾时字符串所构成的编码结果个数。
转移有
当前字符满足条件：
dp[i] = dp[i-1]
前一字符不满足条件：
dp[i] = dp[i-2]
前一字符满足条件且与前一字符构成的当前字符也满足条件：
dp[i] = dp[i-1] + dp[i-2]
class Solution {
public:
int numDecodings(string s) {
int n = s.size();
// 123
// dp[i]表示字符串以i为结尾时字符串所构成的编码结果个数。
// dp[i] = dp[i-1]
// dp[i] = dp[i-2]
// dp[i] = dp[i-1] + dp[i-2]
vector<int> dp(n + 1, 0);
dp[0] = 1;
dp[1] = s[0] == '0' ? 0 : 1;
for (int i = 1; i < n; i++) {
int a = s[i] - '0';
int b = (s[i - 1] - '0') * 10 + s[i] - '0';
if (a >= 1 && a <= 9) dp[i + 1] = dp[i];
if (b >= 10 && b <= 26) dp[i + 1] += dp[i-1];
}
return dp[n];
}
};
空间优化
使用三个变量代替上述的dp[i-1]、dp[i]、do[i+1]。
class Solution {
public:
int numDecodings(string s) {
int n = s.size();
// 123
// dp[i]表示字符串以i为结尾时字符串所构成的编码结果个数。
int f0 = 1;
int f1 = s[0] == '0' ? 0 : 1;
int f2 = f1;
for (int i = 1; i < n; i++) {
f2 = 0;
int a = s[i] - '0';
int b = (s[i - 1] - '0') * 10 + s[i] - '0';
if (a >= 1 && a <= 9) f2 = f1;
if (b >= 10 && b <= 26) f2 += f0;
f0 = f1, f1 = f2;
}
return f2;
}
};
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-04-21，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
