nikunjsoni

91

Jul 10th, 2021
117
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.         // DP array to store the subproblem results
  5.         vector<int> dp(s.length() + 1);
  6.         dp[0] = 1;
  7.  
  8.         // Ways to decode a string of size 1 is 1. Unless the string is '0'.
  9.         // '0' doesn't have a single digit decode.
  10.         dp[1] = s[0] == '0' ? 0 : 1;
  11.  
  12.         for (int i = 2; i < dp.size(); i++) {
  13.             // Check if successful single digit decode is possible.
  14.             if (s[i - 1] != '0')
  15.                 dp[i] = dp[i - 1];
  16.  
  17.             // Check if successful two digit decode is possible.
  18.             int two_digit = stoi(s.substr(i - 2, 2));
  19.             if (two_digit >= 10 && two_digit <= 26) {
  20.                 dp[i] += dp[i - 2];
  21.             }
  22.         }
  23.         return dp[s.length()];
  24.     }
  25. };
RAW Paste Data