LeetCode 0091 - Decode Ways
# Hints
- DP
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
A message containing letters from A-Z
can be encoded into numbers using the following mapping:
'A' -> "1"
'B' -> "2"
...
'Z' -> "26"
To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106"
can be mapped into:
"AAJF"
with the grouping(1 1 10 6)
"KJF"
with the grouping(11 10 6)
Note that the grouping (1 11 06)
is invalid because "06"
cannot be mapped into 'F'
since "6"
is different from "06"
.
Given a string s
containing only digits, return the number of ways to decode it.
The answer is guaranteed to fit in a 32-bit integer.
Example 1:
Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: s = "226"
Output: 3
Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Example 3:
Input: s = "0"
Output: 0
Explanation: There is no character that is mapped to a number starting with 0.
The only valid mappings with 0 are 'J' -> "10" and 'T' -> "20", neither of which start with 0.
Hence, there are no valid ways to decode this since all digits need to be mapped.
Example 4:
Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").
Constraints:
s
contains only digits and may contain leading zero(s).
# 题意
给定一个仅由数字 0-9
组成的字符串 s
,可以将数字串 1-26
映射到字母 A-Z
,不允许用含有前导零的数字串进行映射,求有多少种方法将 s
转化为仅由字母 A-Z
组成的字符串。
# 题解
设 的下标为 。考虑动态规划,设 表示子串 的可行解的数量。
不妨先假设长度为 的任意数字串 00-99
都能合法映射,那么我们可以很容易地写出如下状态转移方程:
则 即为答案。
实际转移时,要分别判断 和 是否为合法可映射的子串,并且一旦出现 则说明无解。
细节问题:
注意特判 的情况。
注意处理各种不存在合法映射的情况。
# AC代码
class Solution {
public:
bool check(char a, char b) {
int x = a - '0', y = b - '0';
int z = x * 10 + y;
return (x != 0 && z >= 1 && z <= 26);
}
int numDecodings(const string & s) {
// 特判
if (s[0] == '0') {
return 0;
}
// 初始化
int n = s.length();
int dp[n + 5];
memset(dp, 0, sizeof(dp));
dp[0] = 1;
dp[1] = 1;
// 递推
for (int i = 2; i <= n; i ++) {
if (s[i - 1] != '0') {
dp[i] += dp[i - 1];
}
if (check(s[i - 2], s[i - 1])) {
dp[i] += dp[i - 2];
}
if (dp[i] == 0) {
return 0;
}
}
// 返回
return dp[n];
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01