Decode Ways

Prereq: Memoization Intro

We have a message to decode. Letters are encoded to digits by its position in the alphabet

A -> 1
B -> 2
C -> 3
...
Y -> 25
Z -> 26

Given a non-empty string of digits, how many ways are there to decode it?

Input: "18"

Output: 2

Explanation: "18" can be decoded as "AH" or "R"

Input: "123"

Output: 3

Explanation: "123" can be decoded as "ABC", "LC", "AW"

Try it yourself