Giải mã cách II trong C ++

Giả sử có một tin nhắn chứa các chữ cái từ A-Z đang được mã hóa thành các số bằng cách ánh xạ sau -

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

Bây giờ, chuỗi được mã hóa cũng có thể chứa ký tự '*', có thể được coi là một trong các số từ 1 đến 9. Vì vậy, nếu chúng ta có thông báo được mã hóa chứa các chữ số và ký tự '*', thì chúng ta phải tìm tổng số cách giải mã nó. Nếu câu trả lời rất dài, chúng ta có thể sử dụng mod 109 + 7 để có kết quả cuối cùng. Vì vậy, nếu đầu vào chỉ là *, thì có thể có 9 cách khả thi, đây đều là các số từ 1 đến 9, vì vậy đây là A đến I.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một hàm add (), hàm này sẽ nhận a, b,
return ((a mod m) + (b mod m)) mod m
Xác định một hàm mul (), điều này sẽ nhận a, b,
return ((a mod m) * (b mod m)) mod m
Từ phương thức chính, hãy làm như sau -
n:=kích thước của s
Xác định một mảng dp có kích thước n + 1
dp [0]:=1
nếu s [0] giống với '0', thì -
- trả về 0
dp [1]:=9 khi s [0] giống với '*' nếu không thì 1
để khởi tạo i:=2, khi i <=n, cập nhật (tăng i lên 1), thực hiện -
- thứ nhất:=s [i - 2], thứ hai:=s [i - 1]
- nếu thứ hai giống với '*', thì -
  - dp [i]:=add (dp [i], mul (9, dp [i - 1]))
- ngược lại khi giây> '0', thì -
  - dp [i]:=dp [i - 1]
- nếu đầu tiên giống với '*', thì -
  - nếu thứ hai giống với '*', thì -
    - dp [i]:=add (dp [i], mul (15, dp [i - 2]))
  - ngược lại khi thứ hai <='6', thì -
    - dp [i]:=add (dp [i], mul (2, dp [i - 2]))
  - Mặt khác
    - dp [i]:=add (dp [i], mul (1, dp [i - 2]))
- nếu không khi đầu tiên giống với '1' hoặc đầu tiên giống với '2', thì -
  - nếu thứ hai giống với '*', thì -
    - nếu đầu tiên giống với '1', thì -
      - dp [i]:=add (dp [i], mul (9, dp [i - 2]))
    - nếu không, khi đầu tiên giống với '2', sau đó -
      - dp [i]:=add (dp [i], mul (6, dp [i - 2]))
  - ngược lại khi (đầu tiên - '0') * 10 + (thứ hai - '0') <=26, thì -
    - dp [i]:=add (dp [i], dp [i - 2])
trả về dp [n]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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*"));
}

Đầu vào

“2*”

Giải mã cách II trong C ++

Ví dụ

Đầu vào

Đầu ra