cheetcode

105. Decode WaysMedium

Count how many ways a numeric string can be decoded into letters.

A message containing letters from A-Z can be encoded into numbers using 1 -> A through 26 -> Z.

Given a string s containing only digits, return the number of ways to decode it.

Examples

Input: s = "12"
Output: 2

Input: s = "226"
Output: 3

Constraints

  • 1 <= s.length <= 100
  • s contains only digits and may contain leading zeroes.