Letter Combinations of a Phone Number — Medium Coding Interview Question

Given a string containing digits from 2-9, return all possible letter combinations that the number could represent (like a telephone keypad). Return empty array for empty input.

Example

Input: digits = "23"

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

Constraints

• 0 ≤ digits.length ≤ 4
• digits[i] is a digit from '2' to '9'

Topics & Companies

Topics: backtracking, hash-map

Asked by: Amazon, Google, Meta, Microsoft, Apple, Bloomberg

Optimal Solution Complexity

Time complexity: O(4^n × n). Space complexity: O(4^n × n).

Practice more

• All DSA Problems
• DSA Patterns