C ++中的解码方式II

假设有一条消息，其中包含来自AZ的字母，正在使用以下映射方式编码为数字-

'A'-> 1，'B'-> 2，...，'Z'-> 26

现在，编码的字符串还可以包含字符“ *”，可以将其视为1到9之间的数字之一。因此，如果我们有包含数字和字符“ *”的编码消息，则必须找到解码方式的总数。如果答案很长，我们可以使用mod 109 + 7来获得最终结果。因此，如果输入仅为*，则可能有9种可能的方式，它们都是1到9的数字，所以它们是A到I。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个函数add()，这将需要a，b，

• return（（a mod m）+（b mod m））mod m

• 定义一个函数mul()，这将需要a，b，

• return（（a mod m）*（b mod m））mod m

• 从主要方法中执行以下操作-

• 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