API tools faq
paste
Advertisement
Fastrail08

Count Encodings

Fastrail08
Jun 12th, 2025
703
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.03 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. /*
  6. QUESTION - https://www.youtube.com/watch?v=jFZmBQ569So&list=PL-Jc9J83PIiG8fE6rj9F5a6uyQ5WPdqKy&index=20 (Count the number of Encodings)
  7. */
  8.  
  9.  
  10. void getEncodings(string digits, string path, vector < char > & encodings) {
  11.     //base case
  12.     //string is empty, which means we have processed all digits
  13.     if (digits.empty()) {
  14.         cout << path << '\n';
  15.         return;
  16.     }
  17.  
  18.     //invalid case
  19.     //If the first char is '0', the prefixes formed by it will be invalid, i.e. '0' & "0i"
  20.     //eg "04356" => prefixes formed => oneChar = '0' & twoChar = "04" which are both invalid, so we can directly return
  21.     if (digits[0] == '0') {
  22.         return;
  23.     }
  24.  
  25.     // levels - digits (the whole string)
  26.     // options - the starting 2 prefixes of digits
  27.  
  28.     // one digit at a time
  29.     int oneChar = stoi(digits.substr(0, 1));
  30.     getEncodings(digits.substr(1), path + encodings[oneChar], encodings);
  31.  
  32.     //two digits at a time
  33.     //we can only get a substring of 2 length if the string is atleast of length = 2
  34.     if (digits.size() >= 2) {
  35.         int twoChar = stoi(digits.substr(0, 2));
  36.         //We can only have this call if twoChar corresponds to a valid encoding
  37.         // substring of length 2, which is: 10 <= twoChar <= 26
  38.         if (twoChar >= 10 && twoChar <= 26) {
  39.             getEncodings(digits.substr(2), path + encodings[twoChar], encodings);
  40.         }
  41.     }
  42. }
  43.  
  44. int getEncodingsMemo(string digits, vector < char > & encodings, unordered_map < string, int > & memo) {
  45.     /*
  46.     The only thing changing here is digits
  47.     So we should be able to memoise the code with a single key = digits.
  48.     Definition = memo(digits) = Number of encodings possible when string = digits.
  49.     */
  50.     if (digits.empty()) {
  51.         return 1;
  52.     }
  53.  
  54.     if (digits[0] == '0') {
  55.         return 0;
  56.     }
  57.  
  58.     //memo Check
  59.     if (memo.count(digits) > 0) {
  60.         return memo[digits];
  61.     }
  62.  
  63.     int totalEncodingsOneChar = 0, totalEncodingsTwoChar = 0;
  64.     //one digit at a time
  65.     int oneChar = stoi(digits.substr(0, 1));
  66.     totalEncodingsOneChar = getEncodingsMemo(digits.substr(1), encodings, memo);
  67.  
  68.     //two digits at a time
  69.     if (digits.size() >= 2) {
  70.         int twoChar = stoi(digits.substr(0, 2));
  71.         // substring of length 2, which is: 10 <= twoChar <= 26
  72.         if (twoChar >= 10 && twoChar <= 26) {
  73.             totalEncodingsTwoChar = getEncodingsMemo(digits.substr(2), encodings, memo);
  74.         }
  75.     }
  76.     return memo[digits] = totalEncodingsOneChar + totalEncodingsTwoChar;
  77. }
  78.  
  79. int getEncodingsDP(string & digits) {
  80.   /*
  81.   Storage & Meaning - dp[i] = Number of encodings possible for strings starting at index i (upto n - 1).
  82.   */
  83.   int n = digits.size();
  84.   vector<int> dp(n, 0);
  85.    
  86.   /*
  87.   Direction - Smallest Problem at: dp[n - 1](string starting at index [n - 1] and ending at [n - 1])
  88.               Largest Problem at: dp[0] (String starting at index 0, original string)
  89.                
  90.   */
  91.   //edge case
  92.   dp[n - 1] = digits[n - 1] == '0' ? 0 : 1;
  93.    
  94.    
  95.   /*
  96.   Travel & Solve - Travel from smallest to largest problem to get the answer to original problem
  97.   */
  98.   for(int i = n - 2; i >= 0; i--){
  99.       if(digits[i] != '0'){
  100.           dp[i] += dp[i + 1];
  101.           if(i <= n - 2){
  102.             int twoCharInt = stoi(digits.substr(i, 2));
  103.             if(twoCharInt >= 10 && twoCharInt <= 26){
  104.                 dp[i] += i == n - 2 ? 1 : dp[i + 2];
  105.             }
  106.           }
  107.       }
  108.      
  109.   }
  110.   return dp[0];
  111. }
  112.  
  113.  
  114.  
  115.  
  116. int main() {
  117.     // your code goes here
  118.     string digits;
  119.     cin >> digits;
  120.  
  121.     vector < char > encodings(27, -1);
  122.     for (int i = 1; i <= 26; i++) {
  123.         encodings[i] = (char)(i - 1 + 'a');
  124.     }
  125.     //Recursive Call with print
  126.     //getEncodings(digits, "", encodings);
  127.  
  128.     //Memo Call
  129.     // unordered_map < string, int > memo;
  130.     // cout << getEncodingsMemo(digits, encodings, memo) << '\n';
  131.     // cout << stoi("03") << '\n';
  132.     //DP Call
  133.     cout << getEncodingsDP(digits) << '\n';
  134. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!