Letter Combinations of a Phone Number — Backtracking Coding Interview Question

In this post, we will go through the classic problem which can be solved using recursion and backtracking (DFS) process. As a bonus, we will also look into the iterative (BFS) solution for this problem.

Problem Statement

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 digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

For example, given the string “23”, the output should be [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

Keypad phone letters to digits mapping

Problem Breakdown

The problem is essentially asking us to generate all combinations from multiple sets of items. In this case, each set corresponds to the possible letters for a particular digit. For instance, the digit 2 corresponds to the letters a, b, and c.

This is a classic computer science problem of generating combinations. It can be approached using recursion or iterative methods.