nikunjsoni

639

Jul 10th, 2021
106
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     int numDecodings(string s) {
  4.         long long int mod = 1000000007;
  5.         int n = s.size();
  6.         vector<long long> dp(n+1);
  7.         dp[0] = 1;
  8.         dp[1] = (s[0] == '*') ? 9 : (s[0] == '0' ? 0 : 1);
  9.        
  10.         for(int i=1; i<n; i++){
  11.             if(s[i] == '*'){
  12.                 dp[i+1] = (9*dp[i])%mod;
  13.                 if(s[i-1] == '1')
  14.                     dp[i+1] = (dp[i+1]+9*dp[i-1])%mod;
  15.                 else if(s[i-1] == '2')
  16.                     dp[i+1] = (dp[i+1]+6*dp[i-1])%mod;
  17.                 else if(s[i-1] == '*')
  18.                     dp[i+1] = (dp[i+1]+15*dp[i-1])%mod;
  19.             }
  20.             else{
  21.                 dp[i+1] = s[i] == '0' ? 0 : dp[i];
  22.                 if(s[i-1] == '1')
  23.                     dp[i+1] = (dp[i+1]+dp[i-1])%mod;
  24.                 else if(s[i-1] == '2' && s[i] <= '6')
  25.                     dp[i+1] = (dp[i+1]+dp[i-1])%mod;
  26.                 else if(s[i-1] == '*')
  27.                     dp[i+1] = (dp[i+1]+ (s[i] <= '6' ? 2:1)*dp[i-1])%mod;
  28.             }
  29.         }
  30.         return dp[n];
  31.     }
  32. };
RAW Paste Data