WaysIIをC++でデコードする

次のマッピング方法を使用して、A〜Zの文字が数字にエンコードされているというメッセージがあるとします-

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

これで、エンコードされた文字列に文字「*」を含めることもできます。これは、1〜9の数字の1つとして扱うことができます。したがって、数字と文字「*」を含むエンコードされたメッセージがある場合は、それをデコードする方法の総数。答えが非常に長い場合は、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つ増やす）、実行-
  • 最初の：=s [i-2]、2番目の：=s [i-1]
  • secondが'*'と同じ場合、-
    • dp [i]：=add（dp [i]、mul（9、dp [i-1]））
  • それ以外の場合、2番目の> '0'の場合、-
    • dp [i]：=dp [i-1]
  • 最初が'*'と同じ場合、-
    • secondが'*'と同じ場合、-
      • dp [i]：=add（dp [i]、mul（15、dp [i-2]））
    • それ以外の場合、2番目の<='6'の場合、-
      • dp [i]：=add（dp [i]、mul（2、dp [i-2]））
    • それ以外の場合
      • dp [i]：=add（dp [i]、mul（1、dp [i-2]））
  • それ以外の場合、最初が「1」と同じか、最初が「2」と同じである場合、次に-
    • secondが'*'と同じ場合、-
      • 最初が「1」と同じ場合、-
        • dp [i]：=add（dp [i]、mul（9、dp [i-2]））
      • それ以外の場合、最初が「2」と同じである場合、次に-
        • dp [i]：=add（dp [i]、mul（6、dp [i-2]））
    • それ以外の場合、（最初の-'0'）* 10 +（2番目の-'0'）<=26の場合、-
      • dp [i]：=add（dp [i]、dp [i-2]）
• return 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