C++で特定のメッセージをデコードするプログラム

整数の文字列であるエンコードされたメッセージが与えられたと仮定します。これで、これらの整数をアルファベットの特定の文字にマッピングできます。 aは1にマップされ、bは2にマップされ、cは3にマップされます。メッセージに含めることができ、1から9までの任意の数字にマップできる文字「*」もあります。したがって、メッセージ「入力」が与えられた場合、それをデコードできる方法がいくつあるかを調べる必要があります。

したがって、入力がinput ="18"のような場合、出力は2になります。

1つは「a」にマップされ、8つは「h」にマップされるため、メッセージは「ah」にデコードできます。また、18は「r」にマップされるため、番号は「r」にマップできます。それで。入力をデコードする方法は全部で2つあります。

これを解決するには、次の手順に従います-

• n：=入力の長さ
• サイズがn+1の配列dynArrを定義し、ゼロで初期化します
• p：=1
• k：='0'
• dynArr [0]：=1
• iを初期化する場合：=1、i <=nの場合、更新（iを1つ増やす）、実行-
  • c：=input [i-1]
  • cが0と同じで、そうでない場合（kは「1」と同じか、kは「2」と同じか、kは「*」と同じ）、-
    • p：=0
    • ループから抜け出す
  • input[i-1]が'*'と同じ場合、-
    • dynArr [i]：=（dynArr [i-1] * 9）mod m
    • kが「1」と同じまたはkが「*」と同じ場合、-
      • dynArr [i]：=（dynArr [i] + dynArr [i-2] * 9）mod m
    • kが「2」と同じまたはkが「*」と同じ場合、-
      • dynArr [i]：=（dynArr [i] +（dynArr [i-2] * 6）mod m）mod m
  • それ以外の場合、
    • cが「0」に等しくない場合、-
    • 
      
      • kが「1」と同じまたはkが「*」と同じ場合、-
        • dynArr [i]：=（dynArr [i] + dynArr [i-2]）mod m
      • if（kは '2'と同じ、またはkは'*'と同じ）およびinput [i --1] <='6'の場合、-
        • dynArr [i]：=（dynArr [i] +（dynArr [i-2]）mod m）mod m
  • k：=c
• pがゼロ以外の場合は、dynArr [n]を返します。それ以外の場合は、0を返します。

例

理解を深めるために、次の実装を見てみましょう-

#include<bits/stdc++.h>

using namespace std;

const long m = 1e9 + 7;

int solve(string input) {
   int n = input.length();
   long long dynArr[n + 1] = {0};

   bool p = 1;
   char k = '0';

   dynArr[0] = 1;
   for (int i = 1; i <= n; i++) {
      char c = input[i - 1];
      if (c == 0 && !(k == '1' || k == '2' || k == '*')) {
         p = 0;
         break;
      }
      if (input[i - 1] == '*') {
         dynArr[i] = (dynArr[i - 1] * 9) % m;
         if (k == '1' || k == '*') dynArr[i] = (dynArr[i] + dynArr[i - 2] * 9) % m;
         if (k == '2' || k == '*') dynArr[i] = (dynArr[i] + (dynArr[i - 2] * 6) % m) % m;
      } else {
         if (c != '0') dynArr[i] = dynArr[i - 1];
         if (k == '1' || k == '*') dynArr[i] = (dynArr[i] + dynArr[i - 2]) % m;
         if ((k == '2' || k == '*') && input[i - 1] <= '6') dynArr[i] = (dynArr[i] + (dynArr[i - 2]) % m) % m;
      }
      k = c;
   }
   return p ? dynArr[n] : 0;
}

int main() {
   cout<< solve("18") <<endl;
   return 0;
}

入力

18

出力

2