数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
服装研究
法律研究C++ 中的解码方式 II
假设有一条消息，包含字母 A-Z，使用以下映射方式编码为数字：
'A' -> 1, 'B' -> 2, ... , 'Z' -> 26
现在，编码的字符串也可以包含字符 '*'，它可以被视为 1 到 9 之间的任何一个数字。因此，如果我们有包含数字和字符 '*' 的编码消息，那么我们必须找到解码它的总方法数。如果答案非常长，我们可以使用模 109 + 7 来获得最终结果。因此，如果输入只有 '*'，则可能有 9 种可能的方式，这些都是 1 到 9 的所有数字，因此这些是 A 到 I。
为了解决这个问题，我们将遵循以下步骤：
- 定义一个函数 add()，它将接收 a, b，
- 返回 ((a mod m) + (b mod m)) mod m
- 定义一个函数 mul()，它将接收 a, b，
- 返回 ((a mod m) * (b mod m)) mod m
- 从主方法执行以下操作：
- n := s 的大小
- 定义一个大小为 n + 1 的数组 dp
- dp[0] := 1
- 如果 s[0] 等于 '0'，则：
- 返回 0
- 如果 s[0] 等于 '*'，则 dp[1] := 9，否则 dp[1] := 1
- 初始化 i := 2，当 i <= n 时，更新 (i 加 1)，执行：
- first := s[i - 2], second := s[i - 1]
- 如果 second 等于 '*'，则：
- dp[i] := add(dp[i], mul(9, dp[i - 1]))
- 否则，如果 second > '0'，则：
- dp[i] := dp[i - 1]
- 如果 first 等于 '*'，则：
- 如果 second 等于 '*'，则：
- dp[i] := add(dp[i], mul(15, dp[i - 2]))
- 否则，如果 second <= '6'，则：
- dp[i] := add(dp[i], mul(2, dp[i - 2]))
- 否则
- dp[i] := add(dp[i], mul(1, dp[i - 2]))
- 如果 second 等于 '*'，则：
- 否则，如果 first 等于 '1' 或 first 等于 '2'，则：
- 如果 second 等于 '*'，则：
- 如果 first 等于 '1'，则：
- dp[i] := add(dp[i], mul(9, dp[i - 2]))
- 否则，如果 first 等于 '2'，则：
- dp[i] := add(dp[i], mul(6, dp[i - 2]))
- 如果 first 等于 '1'，则：
- 否则，如果 (first - '0') * 10 + (second - '0') <= 26，则：
- dp[i] := add(dp[i], dp[i - 2])
- 如果 second 等于 '*'，则：
- 返回 dp[n]
让我们来看下面的实现，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9 + 7;
class Solution {
public:
lli add(lli a, lli b){
return ((a % m) + (b % m)) % m;
}
lli mul(lli a, lli b){
return ((a % m) * (b % m)) % m;
}
int numDecodings(string s) {
int n = s.size();
vector <int> dp(n + 1);
dp[0] = 1;
if(s[0] == '0') return 0;
dp[1] = s[0] == '*' ? 9 : 1;
for(int i = 2; i <= n; i++){
char first = s[i - 2];
char second = s[i - 1];
if(second == '*'){
dp[i] = add(dp[i], mul(9, dp[i - 1]));
}else if(second > '0'){
dp[i] = dp[i - 1];
}
if(first == '*'){
if(second == '*'){
dp[i] = add(dp[i], mul(15, dp[i - 2]));
}else if (second <= '6'){
dp[i] = add(dp[i], mul(2, dp[i - 2]));
}else{
dp[i] = add(dp[i], mul(1, dp[i - 2]));
}
}else if(first == '1' || first == '2'){
if(second == '*'){
if(first == '1'){
dp[i] = add(dp[i], mul(9, dp[i - 2]));
}else if(first == '2'){
dp[i] = add(dp[i], mul(6, dp[i - 2]));
}
}else if((first - '0') * 10 + (second - '0') <= 26){
dp[i] = add(dp[i], dp[i - 2]);
}
}
}
return dp[n];
}
};
main(){
Solution ob;
cout << (ob.numDecodings("2*"));
}输入
“2*”
输出
15
更新于：2020年6月1日
208 次浏览
广告