C ++中的解码方式II
假设有一条消息，其中包含来自AZ的字母，正在使用以下映射方式编码为数字-
'A'->1，'B'->2，...，'Z'->26
现在，编码的字符串还可以包含字符“*”，可以将其视为1到9之间的数字之一。因此，如果我们有包含数字和字符“*”的编码消息，则必须找到解码方式的总数。如果答案很长，我们可以使用mod109+7来获得最终结果。因此，如果输入仅为*，则可能有9种可能的方式，它们都是1到9的数字，所以它们是A到I。
为了解决这个问题，我们将遵循以下步骤-
定义一个函数add()，这将需要a，b，
return（（amodm）+（bmodm））modm
定义一个函数mul()，这将需要a，b，
return（（amodm）*（bmodm））modm
从主要方法中执行以下操作-
n：=s的大小
定义大小为n+1的数组dp
dp[0]：=1
如果s[0]与'0'相同，则-
返回0
dp[1]：=s[0]与'*'相同时为9，否则为1
对于初始化i：=2，当i<=n时，更新（将i增加1），执行-
如果秒与“*”相同，则-
否则，当（first-'0'）*10+（second-'0'）<=26时，则-
dp[i]：=add（dp[i]，mul（6，dp[i-2]））
dp[i]：=add（dp[i]，mul（9，dp[i-2]））
如果第一个与“1”相同，则-
否则，当第一个与“2”相同时，则-
dp[i]：=add（dp[i]，dp[i-2]）
如果秒与“*”相同，则-
否则，当秒<='6'时，则-
除此以外
dp[i]：=add（dp[i]，mul（15，dp[i-2]））
dp[i]：=add（dp[i]，mul（2，dp[i-2]））
dp[i]：=add（dp[i]，mul（1，dp[i-2]））
dp[i]：=dp[i-1]
dp[i]：=add（dp[i]，mul（9，dp[i-1]））
第一：=s[i-2]，第二：=s[i-1]
如果秒与“*”相同，则-
否则，当秒>'0'时，则-
如果第一个与“*”相同，则-
否则，当first与'1'相同或first与'2'相同时，则-
返回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