Given a string that has only positive digits, your task is to decode the string and determine the number of possible ways to decode it. Consider the input string as an encoded message, where each digit in the string represents an alphabet from A to Z (1-26)..

decode-ways.js

function numOfDecodings(decodeStr) {
  const dp = Array(decodeStr.length + 1).fill(0);
  dp[0] = 1;

  // when we are at character (i-1)
  // if it's a valid character, it means that
  // at this point, the number of ways to decode remains the same as it was
  // prior to that character
  // however, if we can also form a double digit from this character (by going left)
  // and if the double digit is valid
  // we also add the number of ways as it was prior to the first character in this double digit
  // so basically we check if the number of ways where this character is treated as single can continue
  // as well as if the number of ways where this character is the last digit in a double digit can continue

  for (let i = 1; i <= decodeStr.length; ++i) {
    const char = decodeStr[i - 1];
    const prevChar = decodeStr[i - 2];

    const digit = parseInt(char);
    if (digit >= 1 && digit <= 26) {
      dp[i] += dp[i - 1];
    }

    if (prevChar != null && prevChar !== "0") {
      const doubleDigit = parseInt(`${prevChar}${char}`);
      if (doubleDigit >= 1 && doubleDigit <= 26) {
        dp[i] += dp[i - 2];
      }
    }
  }

  return dp[decodeStr.length];
}

export { numOfDecodings };

// tc: O(n)
// sc: O(n) (can be improved to O(1) by using two variables instead of the dp arr)