Coding

Letter Combinations of a Phone Number

Asked at

Amazon

Flexport

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given a string consisting of digits from 2 to 9 (inclusive). Return all possible letter combinations that the number can represent.

Mapping of digits to letters is given in first example.

Input : digits = "34" Output : [ "dg", "dh", "di", "eg", "eh", "ei", "fg", "fh", "fi" ] Explanation : The 3 is mapped with "def" and 4 is mapped with "ghi". So all possible combination by replacing the digits with characters are shown in output.

Input : digits = "3" Output : [ "d", "e", "f" ] Explanation : The 3 is mapped with "def".

Input : digits = "8"

1 <= digits.length <= 4
digts[i] contains digitd from [2,9].

cpp

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        //your code goes here
    }
};

java

class Solution {
    public List<String> letterCombinations(String digits) {
        //your code goes here
    }
}

python

class Solution:
    def letterCombinations(self, digits):
        #your code goes here

javascript

class Solution {
    letterCombinations(digits) {
        //your code goes here
    }
}

csharp

public class Solution
{
    public IList<string> LetterCombinations(string digits)
    {
        //your code goes here
    }
}

func letterCombinations(digits string) []string {
	//your code goes here
}

Stuck? Show a way to structure it+

01Create the digit-to-letters lookup.
02Return an empty list for empty input.
03Append each mapped letter at a position.
04Recurse to the next digit and backtrack.
05Emit the path after all digits are consumed.

Reference answer

Map digits 2 through 9 to their keypad strings, then build one candidate string per recursion branch. The recursion index identifies the next digit. If it equals the input length, append the current built string to the result. Otherwise iterate every letter mapped from digits[index], append it, recurse with index plus one, and remove it afterward. An empty input should normally return an empty list rather than a list containing the empty string, so handle it before DFS. The branching factor is three or four, which makes runtime inherently proportional to output: O(4 to the power n times n) in the worst case because each completed string of length n is copied. The call stack and mutable path use O(n) space excluding results. State assumptions if inputs may contain zero or one because they lack standard letter mappings.

Then expect these follow-ups

How would you stream combinations instead of storing them?
Tests: constraint adaptation
How do you support a custom keypad mapping?
Tests: follow-up reasoning

Hiring now

Flexport has 115 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Software Engineer II, Autonomous Freight Technology
Bellevue, Washington, United States
Software Engineer II, DevEx
Amsterdam, Netherlands
Staff Software Engineer, DevEx
Amsterdam, Netherlands

Or practice this question first

Next question