C++에서 방법 II 디코딩

<시간/>

A-Z의 문자가 포함된 메시지가 다음 매핑 방법을 사용하여 숫자로 인코딩되고 있다고 가정합니다. -

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

이제 인코딩된 문자열에는 1에서 9 사이의 숫자 중 하나로 처리될 수 있는 '*' 문자도 포함될 수 있습니다. 따라서 숫자와 '*' 문자가 포함된 인코딩된 메시지가 있는 경우 다음을 찾아야 합니다. 그것을 디코딩하는 총 방법 수. 답변이 매우 길면 mod 109 + 7을 사용하여 최종 결과를 얻을 수 있습니다. 따라서 입력이 *만 있으면 가능한 9가지 방법이 있을 수 있습니다. 이들은 모두 1에서 9까지의 숫자이므로 A에서 I입니다.

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

add() 함수를 정의하면, b,
return ((a mod m) + (b mod m)) mod m
mul() 함수를 정의하면, 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], 두 번째 :=s[i - 1]
- 초가 '*'와 같으면 -
  - dp[i] :=add(dp[i], mul(9, dp[i - 1]))
- 그렇지 않으면 초> '0'일 때 -
  - dp[i] :=dp[i - 1]
- 먼저 '*'와 같으면 -
  - 초가 '*'와 같으면 -
    - dp[i] :=add(dp[i], mul(15, dp[i - 2]))
  - 그렇지 않으면 두 번째 <='6'일 때 -
    - dp[i] :=add(dp[i], mul(2, dp[i - 2]))
  - 그렇지 않으면
    - dp[i] :=add(dp[i], mul(1, dp[i - 2]))
- 그렇지 않으면 first가 '1'과 같거나 first가 '2'와 같을 때 -
  - 초가 '*'와 같으면 -
    - 먼저 '1'과 같으면 -
      - dp[i] :=add(dp[i], mul(9, dp[i - 2]))
    - 그렇지 않으면 처음이 '2'와 같을 때 -
      - dp[i] :=add(dp[i], mul(6, dp[i - 2]))
  - 그렇지 않으면 (첫 번째 - '0') * 10 + (두 번째 - '0') <=26일 때 −
    - dp[i] :=add(dp[i], dp[i - 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*”

C++에서 방법 II 디코딩

예시

입력

출력