0. Problem

We want to find the number of ways to convert the string of numbers into letters.

1. Recursion

To find a recursion, you should focus on the first few letters of the string. Say you're given this string:

To convert the string into letters, you can convert the first number "1" as a letter. You can also consider the first two numbers "12" as a letter. You can then convert the remaining strings into letters. This gives the recursion:

You can generalize this to find a recursion. You need to make sure you only convert numbers "1" through "26" into letters, otherwise you should set the number of ways equal to zero. For example, you cannot convert the string "0" or "34" into a singe letter because they don't correspond to a letter a through z. Here's the recursion for this:

It's better to recurse on numbers than strings:

2. Base case

The recursion calls itself on smaller and smaller strings. In this problem, we need to find two base cases, because the function numWays(i) calls two functions numWays(i+1) and numWays(i+2).

The first base case is that there is 1 way to get to the empty string "":

We also need another base case. The easiest thing to do is just say there are 0 ways to get to i = len(s)+1, because this case is nonsensical so it should be ignored:

3. Code

To code this up, we should use Dynamic Programming and compute all of the function calls in the order that they're needed. We can do this by computing small i first and big i last.

Time Complexity $O(n)$

Space Complexity $O(n)$