[LeetCode 91] Decode Ways
题目
A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.
测试案例
Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
思路
本题的主要细节是；对当前一位进行解码时，当前位不能为0对当前两位进行解码时，当前两位数的值应大于9且小于27.
代码如下
class Solution {
public int numDecodings(String s) {
int n = s.length(), pre, cur;
if(n == 0){
return 0;
}
int[] nums = new int[n + 1];
nums[0] = 1;
nums[1] = s.charAt(0) == '0' ? 0 : 1;
for(int i = 2; i <= n; i++){
pre = s.charAt(i - 2) - '0';
cur = s.charAt(i - 1) - '0';
if(cur > 0){
nums[i] += nums[i - 1];
}
int value = pre * 10 + cur;
if(value > 9 && value < 27){
nums[i] += nums[i - 2];
}
}
return nums[n];
}
}
[LeetCode 639] Decode Ways II
题目
A message containing letters from A-Z is being encoded to numbers using the following mapping way:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Beyond that, now the encoded string can also contain the character '*', which can be treated as one of the numbers from 1 to 9.
Given the encoded message containing digits and the character '*', return the total number of ways to decode it.
Also, since the answer may be very large, you should return the output mod 10^9 + 7.
Note:
The length of the input string will fit in range [1, 10^5].
The input string will only contain the character '*' and digits '0' - '9'.
测试案例
Input: "*"
Output: 9
Explanation: The encoded message can be decoded to the string: "A", "B", "C", "D", "E", "F", "G", "H", "I".
Input: "1*"
Output: 9 + 9 = 18
思路
- 对当前位进行解码时，当前位分：0，1~9，*三种情况进行讨论。
- 对当前两位进行解码时，当前两位分：
- 全为*：有 15nums[i - 2] 种情况
- *非*：个位介于0~6之间时，有 2nums[i - 2] 种情况；个位大于6时，有 nums[i - 2] 种情况
- 十位为非*，个位为*：十位分 0或3~9，1，2 三种情况考虑。
- 均非*：两位数要大于9，且小于的等于26.
代码如下
class Solution {
public int numDecodings(String s) {
final int MODULE = 1_000_000_000 + 7;
int n = s.length(), pre, cur, value;
if(n == 0){
return 0;
}
long[] nums = new long[n + 1];
nums[0] = 1;
char ch;
if((ch = s.charAt(0)) == '0'){
nums[1] = 0;
}
else if(ch == '*'){
nums[1] = 9;
}
else{
nums[1] = 1;
}
for(int i = 2; i <= n; i++){
pre = s.charAt(i - 2);
cur = s.charAt(i - 1);
long temp = 0;
if(cur >= '1' && ch <= '9'){
temp = nums[i - 1];
}
else if(cur == '*'){
temp = 9 * nums[i - 1];
}
nums[i] = (nums[i] + temp) % MODULE;
temp = 0;
if(pre != '*' && cur != '*'){
value = (pre - '0') * 10 + cur - '0';
if(value > 9 && value < 27){
temp = nums[i - 2];
}
}
else if(cur == '*' && pre != '*'){
if(pre == '1'){
temp = 9 * nums[i - 2];
}
else if(pre == '2'){
temp = 6 * nums[i - 2];
}
}
else if(pre == '*' && cur != '*'){
if(cur < '7'){
temp = 2 * nums[i - 2];
}
else{
temp = nums[i - 2];
}
}
else{
temp = 15 * nums[i - 2];
}
nums[i] = (nums[i] + temp) % MODULE;
}
return (int)nums[n];
}
}