Decode Ways

Letters are encoded as A = 1 … Z = 26. Given a string of digits, return how many ways it can be decoded.

A way to picture it

You intercept a secret message with the spaces removed. "226" could be 2-2-6, 22-6 or 2-26. At every digit, ask two questions: can it stand alone as a letter, and can it pair with the digit before it?

How to approach it

ways(i) = (digit i−1 is 1–9 ? ways(i−1) : 0) + (last two digits are 10–26 ? ways(i−2) : 0), with ways(0) = 1.

Example

Input: {"s":"12"}. Output: 2.

Complexity: O(n) time and O(1) space. One pass; only the last two counts are needed.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.