Solving the 'Letter Combinations of a Phone Number' Problem with TypeScript

The classic "Letter Combinations of a Phone Number" problem reminds me of the good ol' days where sending a text message involved multiple key presses on my old Nokia 3110 keypad. Nostalgia aside, this algorithmic problem serves as an excellent exercise in recursion, backtracking, and even iterative solutions.

In this article, I'll delve into these different methodologies for solving the problem, including writing and sharing examples using JavaScript/TypeScript. Solving this problem isn't just an academic curiosity; knowing how to generate combinations from sets is a real‑world need with various applications, particularly in web development.

The Problem

Given a string containing digits from 2‑9 inclusive, we need to return all possible letter combinations that the number could represent. A mapping of digits to letters (just like on a telephone button) is given, where:

2 -> 'abc'3 -> 'def'4 -> 'ghi'5 -> 'jkl'6 -> 'mno'7 -> 'pqrs'8 -> 'tuv'9 -> 'wxyz'

If you're as old as I am, you would be familiar with this from the early noughties, when your phone keypad looked a bit like this (note that 1 doesn't map to any letters):

Example Outputs

Input: 23
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

Input: 9
Output: ["w", "x", "y", "z"]

Potential Solution Methods

As with any coding problem, there are any number of different ways to approach and solve this one. Today, I'd like to explore the following techniques:

1. Recursion
2. Backtracking
3. Iterative Method

Setting up the Data

Before delving into the solutions, there is one thing they all share, and that's a map of the relationship between numbers and letters. This is best structured as a TypeScript object which maps each digit from 2 to 9 to an array of characters that each represents:

const phoneMap: { [key: string]: string[] } = {  2: ['a', 'b', 'c'],  3: ['d', 'e', 'f'],  4: ['g', 'h', 'i'],  5: ['j', 'k', 'l'],  6: ['m', 'n', 'o'],  7: ['p', 'q', 'r', 's'],  8: ['t', 'u', 'v'],  9: ['w', 'x', 'y', 'z'],};

1. Recursion

Recursion aligns naturally with the structure of the problem, so it's a sensible starting point for a solution.

In the recursive approach, we start by mapping each digit to its corresponding letters (this is phoneMap which I've described above). We then call a recursive function that takes the current combination of letters and the next digits to check.

The Code

Here's how that looks in TypeScript:

const letterCombinations = (digits: string): string[] => {  if (digits === '') return [];  const result: string[] = [];  const recurse = (index: number, current: string) => {    if (index === digits.length) {      result.push(current);      return;    }    for (const letter of phoneMap[digits[index]]) {      recurse(index + 1, current + letter);    }  };  recurse(0, '');  return result;};

How It Works

Once initialised using an empty string, there are two potential two cases:

• Base Case:

  If there are no more digits to check, we add the current combination to our result list.

• Recursive Case:

  Otherwise, for each letter that the next digit maps to, append it to the current combination and call the function recursively.

2. Backtracking

Backtracking is very similar to the recursive approach. However, it adds the opportunity to "undo" a choice where it doesn't lead to a solution.

The Code

In TypeScript, this would look like this:

const letterCombinations = (digits: string): string[] => {  if (digits === '') return [];  const result: string[] = [];  const backtrack = (index: number, current: string[]) => {    if (index === digits.length) {      result.push(current.join(''));      return;    }    for (const letter of phoneMap[digits[index]]) {      current.push(letter);      backtrack(index + 1, current);      current.pop();    }  };  backtrack(0, []);  return result;};

How It Works

1. We start the function with the current combination and next digits to examine.
2. For each letter that a digit can map to, we append it to our current combination and proceed recursively.
3. If we reach a state where we know a solution couldn't be possible (though for this problem, that's unlikely), we backtrack by removing the last character of our current combination before making the next choice.

This allows us to explore all possible combinations in a very structured manner, although at the potential cost of performance.

3. Iterative Method

Unlike the (closely‑related) previous two methods, using an iterative approach means we remove the need for recursion from our function and can generally be more memory‑efficient. However, this comes at the expense of intuition; it's a harder concept to grasp initially, and in a real‑world codebase, it could leave your colleagues unsure of what you've written or how it works.

The Code

Here's what that would look like in TypeScript:

const letterCombinations = (digits: string): string[] => {  if (digits === '') return [];  let result: string[] = [''];  for (const digit of digits) {    const newResult: string[] = [];    for (const combo of result) {      for (const letter of phoneMap[digit]) {        newResult.push(combo + letter);      }    }    result = newResult;  }  return result;};

How It Works

1. We initiate a queue and populate it with the initial letters mapped from the first digit.
2. Then we go digit by digit, dequeuing an element from the front, appending each letter that the next digit maps to, and enqueuing it back.
3. We continue this process until the queue contains combinations that are as long as the input digits.

Wrapping up

Among the three methods, recursion and backtracking are more intuitive but essentially do the same thing. The iterative method is less straightforward but avoids the overhead of recursive calls. Whilst each approach has its pros and cons, (depending on the specific requirements of the task at hand), understanding the details of each can empower you to make a more informed choice and a more well‑rounded developer.