Problem 🤔

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Note

• 1 does not map to any letters.

Let’s look at an example.

Example 1

Input: 2

Output: ['a', 'b', 'c']

Input: 23

Output:

Real World Applications 🌎

Have you wondered how mappings to numbers like 1800 - HEY - BUSINESS? I have! Let’s break it down.

The Finer Details 🔎

Problems like these can be elegantly solved using recursion and backtracking. Why? There are many options here, and choosing one letter sets us down a specific path. Of course, because we need need to return all of the options we need to backtrack here once committing to a letter. Let’s look at a simple recursive approach as well as the backtracking one.

Recursive Solution 💡

Building all the different options definitley seems like something that can be written elegantly with recursion! Let’s give it a try.

Base Case

If our digits only holds a single digit we know what to return! Just a mapping of all the possibilities for that letter.

2 -> ['a', 'b', 'c'] 3 -> ['d', 'e', 'f'] 4 -> ['g', 'h', 'i']

Easy!

Recurrence Relation

Now, we are only tasked with making the input smaller, as we have a recursive method which can handle the rest! Let’s make the input smaller by calling the recursive method without the last letter.

Complexity Analysis 🧮

Time complexity

O(3^N * 4*m)

N is the number of digits in the input that maps to 3 letters (e.g. 2, 3, 4, 5, 6, 8) and M is the number of digits in the input that maps to 4 letters (e.g. 7, 9)

Space complexity

O(3^N * 4*m)

Hold all options in result list..

Backtracking Solution 💡

Before solving this I recommend reviewing Recursion! Specifically, generating subsets of size k! You can check that out here.

Complexity Analysis 🧮

Time complexity

O(3^N * 4*m)

N is the number of digits in the input that maps to 3 letters (e.g. 2, 3, 4, 5, 6, 8) and M is the number of digits in the input that maps to 4 letters (e.g. 7, 9)

Space complexity

O(3^N * 4*m)

Hold all options in result list.

Optimal Iterative Solution 💡

We saw two recursive based solutions. But do we actually need recursion to compute all the options? What if we built the final result iteratively? I think this becomes easier to imagine when we look at the example given above.

Example

Input: 23

Output

Let’s break it down by iterations. On the first iteration we could simply add each letter, as they all could be the first letter in the string:

Now, in a nested for loop we can append the next char to each item already in our output. If we do this iterativetly for each char in our input we’re good to go

Takeaways 🎉🥳

• When encountering problems with exponential possibilities, that require output generation, consider recursion and backtracking!
• Generating subsets, permutations and power sets are common problems. Their applications often creep up in real life, like in this problem. It is well worth internalizing how to solve these problems as they are a great asset, and let you sound cool when you can explain phone number / word mappings.

Resources 📚 💻

Leetcode