欢迎访问LeetCode题解合集
题目描述
一条包含字母 A-Z
的消息通过以下映射进行了 编码 :
'A' -> 1
'B' -> 2
...
'Z' -> 26
要 解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法)。例如,"111"
可以将 "1"
中的每个 "1"
映射为 "A"
,从而得到 "AAA"
,或者可以将 "11"
和 "1"
(分别为 "K"
和 "A"
)映射为 "KA"
。注意,"06"
不能映射为 "F"
,因为 "6"
和 "06"
不同。
给你一个只含数字的 非空 字符串 num
,请计算并返回 解码 方法的 总数 。
题目数据保证答案肯定是一个 32 位 的整数。
示例 1:
输入:s = "12"
输出:2
解释:它可以解码为 "AB"(1 2)或者 "L"(12)。
示例 2:
输入:s = "226"
输出:3
解释:它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
示例 3:
输入:s = "0"
输出:0
解释:没有字符映射到以 0 开头的数字。含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。由于没有字符,因此没有有效的方法对此进行解码,因为所有数字都需要映射。
示例 4:
输入:s = "06"
输出:0
解释:"06" 不能映射到 "F" ,因为字符串开头的 0 无法指向一个有效的字符。
提示:
- $1 \le s.length \le 100$
s
只包含数字,并且可能包含前导零。
题解:
动态规划。
设 f[i]
表示 s
的前 i
个字符解码方案数,分以下几种情况:
-
若
s[i] == '0'
,0
只能与前面的数字捆绑在一起,所以考虑s[i-1]
:1.若
s[i-1] == '0'
,两个连续的0
是非法的,直接返回0
2.若s[i-1] > '2'
,因为合法的只有"10"
和"20"
,所以此时也是非法的,返回0
3.否则的话,f[i] = f[i - 2]
,将'0'
与s[i - 1]
捆在一起 -
若
s[i] != '0'
:1.若
s[i - 1]
与s[i]
组成的十进制值处于10~26
范围,则可以捆绑,此时f[i] = f[i - 1] + f[i - 2]
;
2.否则的话,s[i]
只能自成一派了,f[i] = f[i - 1]
时间复杂度:$O(n)$
额外空间复杂度:$O(n)$
class Solution {
public:
int numDecodings(string s) {
if ( s[0] == '0' ) return 0;
vector<int> f(s.size() + 1);
f[0] = f[1] = 1;
int val;
for ( int i = 2; i <= s.size(); ++i ) {
if ( s[i - 1] == '0' ) {
if ( s[i - 2] == '0' || s[i - 2] > '2' ) return 0;
f[i] = f[i - 2];
} else {
f[i] = f[i - 1];
val = (s[i - 2] & 15) * 10 + (s[i - 1] & 15);
if ( val >= 10 && val <= 26 ) f[i] += f[i - 2];
}
}
return f[s.size()];
}
};
/*
时间:0ms,击败:100.00%
内存:6MB,击败:86.37%
*/
可以发现 f[i]
只跟 f[i - 1]
和 f[i - 2]
有关,可以使用两个变量保存 f[i - 1]
和 f[i - 2]
:
class Solution {
public:
int numDecodings(string s) {
if ( s[0] == '0' ) return 0;
int f1 = 1, f2 = 1;
int val, now = 0;
for ( int i = 2; i <= s.size(); ++i ) {
if ( s[i - 1] == '0' ) {
if ( s[i - 2] == '0' || s[i - 2] > '2' ) return 0;
now = f2;
} else {
now = f1;
val = (s[i - 2] & 15) * 10 + (s[i - 1] & 15);
if ( val >= 10 && val <= 26 ) now += f2;
}
f2 = f1;
f1 = now;
}
return f1;
}
};
/*
时间:0ms,击败:100.00%
内存:6MB,击败:93.14%
*/