Source: https://leetcode.com/problems/decode-ways/

A message containing letters from A-Z can be encoded into numbers using the following mapping: A - 1 B - 2 ... Z - 26 To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, 11106 can be mapped into: AAJF with the grouping (1 1 10 6) KJF with the grouping (11 10 6) Note that the grouping (1 11 06) is invalid because 06 cannot be mapped into F since 6 is different from 06. Given a string s containing only digits, return the number of ways to decode it. The test cases are generated so that the answer fits in a 32-bit integer

/**
* @param {string} s
* @return {number}
*/
// Recursion Approach
// A character may be decoded alone if (1-9) or as a pair (1 and 0-9) or (2 and 0-6)
// If current index is equal to s.length, return 1 (we decoded a valid message in reaching the end)
// If the character is 0 we can return 0 as it can't be leading
// Recursively keep track of the result and decode the next character
// Recursively keep track of the result and decode the characters after the valid pair if the current index is less than s.length - 1
// and the current number is 1 or the current number is 2 and followed by 0-6
// O(2^n) time cause we have two choices: either decode 1 character or a pair at a time
var numDecodings = function(s) {
 const messageLength = s.length;
 const rec = (currentIndex) => {
   // Reached the end of a valid decoded message, return 1 to the count
   if (currentIndex === messageLength) {
     return 1;
   }
   // Can't have any leading zeroes, return 0
   if (s[currentIndex] === '0') {
     return 0;
   }
   // Recursively decode the next character
   let count = rec(currentIndex + 1);
   
   // Recursively decode the characters after the valid pair
   if (currentIndex < messageLength - 1 && (s[currentIndex] === '1' || (s[currentIndex] === '2' && s[currentIndex+1] < '7'))) {
     count += rec(currentIndex + 2);    
   }
   
   return count;
 };
 
 return rec(0);
};