C++에서 주어진 메시지를 디코딩하는 프로그램

<시간/>

정수 문자열인 인코딩된 메시지가 주어졌다고 가정합니다. 이제 이러한 정수를 알파벳의 특정 문자에 매핑할 수 있습니다. a는 1에 매핑되고, b는 2에 매핑되고, c는 3에 매핑되는 식입니다. 메시지에 있을 수 있고 1에서 9까지의 숫자에 매핑될 수 있는 문자 '*'도 있습니다. 따라서 메시지 '입력'이 주어지면 메시지를 해독할 수 있는 방법의 수를 찾아야 합니다.

따라서 입력이 입력 ="18"과 같으면 출력은 2가 됩니다.

메시지는 1이 "a"에 매핑되고 8이 "h"에 매핑되므로 "ah"로 디코딩될 수 있습니다. 또한 18이 "r"에 매핑되는 것처럼 숫자는 "r"에 매핑될 수 있습니다. 그래서. 입력을 디코딩할 수 있는 방법은 총 2가지가 있습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=입력 길이
배열 dynArr을 n+1 크기로 정의하고 0으로 초기화
p :=1
k :='0'
dynArr[0] :=1
초기화 i :=1의 경우, i <=n일 때 업데이트(i를 1만큼 증가), 수행 -
- c :=입력[i - 1]
- c가 0과 같지 않고(k가 '1'과 같거나 k가 '2'와 같거나 k가 '*'와 같은 경우) -
  - p :=0
  - 루프에서 빠져나오기
- 입력[i - 1]이 '*'와 같으면 −
  - dynArr[i] :=(dynArr[i - 1] * 9) 모드 m
  - k가 '1'과 같거나 k가 '*'와 같으면 −
    - dynArr[i] :=(dynArr[i] + dynArr[i - 2] * 9) 모드 m
  - k가 '2'와 같거나 k가 '*'와 같으면 −
    - dynArr[i] :=(dynArr[i] + (dynArr[i - 2] * 6) 모드 m) 모드 m
- 그렇지 않으면
  - c가 '0'과 같지 않으면 -
  - - k가 '1'과 같거나 k가 '*'와 같으면 −
      - dynArr[i] :=(dynArr[i] + dynArr[i - 2]) 모드
    - 만약 (k가 '2'와 같거나 k가 '*'와 같다) 그리고 input[i - 1] <='6'이면 −
      - dynArr[i] :=(dynArr[i] + (dynArr[i - 2]) 모드 m) 모드 m
- k :=c
p가 0이 아니면 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;
}