Recursion

All Interpretations

Given a string of numbers numbers, return all the possible ways you can interpret the string as a sequence of letters.

You can convert any number into its corresponding letter in the alphabet.

"1" <--> "a",
"2" <--> "b",
"3" <--> "c",
...
"25" <--> "y",
"26" <--> "z"

First Few Test Cases:

allInterpretations('13')
# ['ac', 'm']

allInterpretations('123')
# ['abc', 'aw', 'lc']

allInterpretations('1001')
# []

In order to solve this problem, we want to write a recursion that visits every possible string we can interpret, given the original string of numbers numbers. We need to keep track of the current string of letters we've interpreted so far, which we'll call letters.

visitAll(numbers, letters)

1. Recursion

As usual, we find the recursion by focusing on the first characters in the string. You can interpret the first character as a letter if it's between "1", and "9", or you can interpret the first two characters as a letter if they're between "10" and "26". Here's the recursion for this:

# letterOf("1") = "a"
# letterOf("26") = "z"

visitAll(numbers, letters) = (

    # if first character is "1" through "9"
    if numbers[:1] in ["1", "2", ..., "9"]:
        visitAll(numbers[1:], letters + letterOf(numbers[:1]))
    
    # first two characters are "10" through "26"
    if numbers[:2] in ["10", "11", ..., "26"]:
        visitAll(numbers[2:], letters + letterOf(numbers[:2]))
)

It's slow to recurse on the numbers string like this, since strings are immutable, and every time you add/remove a letter you create a whole new string. You can fix this by recursing on the index i in the string, instead of on the full string itself. We'll also use Backtracking and make the letters input into a global array so that you can append and pop from it quickly. We'll also make the index i into a global parameter, but this isn't needed.

# global parameters
i = 0
letters = []

visitAll() = (
    # first character is "1" through "9"
    if numbers[i:i+1] in ["1", "2", ..., "9"]:
        letters.append(letterOf(numbers[i:i+1]))
        i += 1
        visitAll()
        i -= 1
        letters.pop()

    # first two characters are "10" through "26"
    if numbers[i:i+2] in ["10", "11", ..., "26"]:
        letters.append(letterOf(numbers[i:i+2]))
        i += 2
        visitAll()
        i -= 2
        letters.pop()
)

2. Base case

When the whole string has been interpreted, we know we have a solution. This happens when i is at the end of the string. In this case, we should add the current interpretation that we have letters as one of the answers to the problem.

if i==len(numbers) or i==len(numbers)+1:
    answer.append("".join(letters))

3. Code

Here's the code you get, combining the recursion and base case:

def allInterpretations(numbers):

    # hashmaps for fast lookups
    AthruZ = "abcdefghijklmnopqrstuvwxyz"
    letterOf = {str(i+1): AthruZ[i] for i in range(26)} # "number" -> "letter"
    nums1to9 = {str(i) for i in range(1, 10)}
    nums10to26 = {str(i) for i in range(10, 27)}
    
    
    # global parameters
    i = 0
    letters = []
    answer = []
    
    def visitAll():
        # nonlocal lets us set global variables from inside the function
        nonlocal i, letters, answer

        # base case
        if i==len(numbers) or i==len(numbers)+1:
            answer.append("".join(letters))
            return

        # recursion
        if numbers[i:i+1] in nums1to9:
            letters.append(letterOf[numbers[i:i+1]])
            i += 1
            visitAll()
            i -= 1
            letters.pop()

        if numbers[i:i+2] in nums10to26:
            letters.append(letterOf[numbers[i:i+2]])
            i += 2
            visitAll()
            i -= 2
            letters.pop()
    
    visitAll() # call visitAll to compute answer
    return answer

Time Complexity $O(\texttt{n} \cdot 2^\texttt{n})$ . There are $O(2^\texttt{n})$ entries in the final array, and each entry is of size $O(\texttt{n})$ , where n is the size of the input.

Space Complexity $O(\texttt{n} \cdot 2^\texttt{n})$ for the answer array. The Call Stack gets to size $O(\texttt{n})$ and letters does too, but both of these are negligible compared to the answer array.

Mark as Completed:

Submits:

allInterpretations

Test your code to get an output here!

allInterpretations(

)

Test your code to get an output here!