Letter Combinations of a Phone Number

Letter Combinations of a Phone Number is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Backtracking Patterns pattern, in the Subsets (Include/Exclude) subpattern.

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.

Example 1:

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

Example 2:

Input: digits = "" Output: []

Example 3:

Input: digits = "2" Output: ["a","b","c"]

Constraints:

- 0 <= digits.length <= 4

- digits[i] is a digit in the range ['2', '9'].

Topics and companies

Topics: Hash Table, String, Backtracking.

Reported in interviews at Amazon, Microsoft, Twilio, Facebook, Capital One, eBay, Google, Uber, Apple, Oracle, JPMorgan, Morgan Stanley and others.

How to practise Letter Combinations of a Phone Number on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n * 4^n) time and O(1) space.

Open Letter Combinations of a Phone Number in the code editor, or read the Letter Combinations of a Phone Number editorial for a worked solution with its approach and complexity analysis.

Where Letter Combinations of a Phone Number sits in the DSA pattern sheet

• Backtracking Patterns pattern guide
• Subsets (Include/Exclude) subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Letter Combinations of a Phone Number

Other problems that use the same Subsets (Include/Exclude) and Backtracking Patterns techniques:

• Combinations — Medium, same subpattern
• Subsets — Medium, same subpattern
• Subsets II — Medium, same subpattern
• Check if Word Can Be Placed In Crossword — Medium, same pattern
• Combination Sum — Medium, same pattern
• Combination Sum II — Medium, same pattern