Skip to main content

0017 - Letter Combinations of a Phone Number (Medium)

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 11 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 = ""
Output: ["a","b","c"]


  • 0 <= digits.length <= 4
  • digits[i] is a digit in the range ['2', '9'].

Approach 1: Recursive Backtracking with Subsets

Simple and naive approach to solve this problem by having map of key and values same as Phone key pad.

Iterative over the input digit by digit and for each digit look for the combinations of key characters. Initialize prefix string which holds an key combination in the recursive call stack.

As per example 1, digits is 2323, for the first digit 22, the program iterates over "abc" characters, and for each char, the program is recursively called to get the next digit combination associated with current character 'a'.

Maximum possibilities for each character is 44, So each of recursive call, adds the char to the prefix string and add it to the result list, it does O(n)O(n) time, and O(4n)O(4^n) recursive call stack for each character, where nn is the length of the string.

Time complexity: O(nn)O(n ^ n) or O(n4n)O(n * 4^n)

Space complexity: O(nn)O(n^n) or O(4n)O(4 ^ n)

Written by @vigneshshiv
class Solution {

private Map<Character, String> digitToChar = Map.of(
'2', "abc",
'3', "def",
'4', "ghi",
'5', "jkl",
'6', "mno",
'7', "pqrs",
'8', "tuv",
'9', "wxyz"

public List<String> letterCombinations(String digits) {
if (digits.length() == 0) {
return new ArrayList<>();
List<String> result = new ArrayList();
backtrack(digits, result, "", 0);
return result;

public void backtrack(String digits, List<String> result, String prefix, int index) {
if (prefix.length() == digits.length()) {
} else if (index >= digits.length()) {
} else {
String digit = digitToChar.get(digits.charAt(index));
for (char c : digit.toCharArray()) {
backtrack(digits, result, prefix + c, index + 1);

Approach 2: Recursive Backtracking with ASCII

Instead of having a map of characters for each digits, try to solve the problem only with numbers.

Try to map every digits to ASCII combinations like 22 is mapped "abc", How to get this from the number.

Based on the input, we need to have a start and end range for each digit. To form 'a' from 22, which number we can add to get 'a', if we add 00 with char 'a' then we will get the same char 'a', like wise we need to form the range for other digits as well.

For 77 and 99 key pads has 4 chars, so apply the logic by bit different as mentioned below in the program.

Time and Space complexity is same as above.

Written by @vigneshshiv
class Solution {

public List<String> letterCombinations(String digits) {
if (digits.isEmpty()) {
return new ArrayList<>();
return letterCombinations("", digits);

public List<String> letterCombinations(String prefix, String digits) {
List<String> result = new ArrayList<>();
if (digits.isEmpty()) {
return result;
// Transform char to number by subtracting '0' char (ASCII)
int digit = (int) digits.charAt(0) - '0';
// ASCII start range for the current digit
int start = digit > 7 ? (digit - 1) * 3 - 2 : (digit - 2) * 3;
// End range
int end = digit == 9 ? (digit * 3) - 1 : digit > 6 ? (digit * 3) - 2 : (digit - 1) * 3;
for (int i = start; i < end; i++) {
char ch = (char) ('a' + i);
result.addAll(letterCombinations(prefix + ch, digits.substring(1)));
return result;

Approach 3: Iterative Backtracking

We can utilize the same pricinple as above, just maintaining our own stack. At each step of our backtracking, we add to our stack, our current string plus 1 of the mapped letters and we do that for all mapped letters. When we run out of digits we can add to our return array the completed string.

Time Complexity: O(n4n)O(n * 4^n) Where n is the length of the input string. In the worst case, (all 7s or 9s) we will have 4 choices of letters to choose from and for each output string we create will be of size nn and therefore take O(n)O(n) time to create the string.

Space Complexity: O(4n)O(4^n). We will end up creating 4n4^n output strings to add to our return array.

Written by @ColeB2
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
# base case, given empty input string, return early.
if not digits:
return []
# initialize our digit to letter map.
letter_map = {
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz"
# intiailize our return list, and stack.
letter_combos = []
# stack is formatted as (int, str)
# where the int is our index inside the digits string.
# and the str is the current string created so far.
stack = [(0, "")]

while stack:
# pop off the current index, and the current string.
idx, string = stack.pop()
# if we reached the end of the digits string.
if idx == len(digits):
# add to our return list, the string we created and continue.
# for each character that the current digit maps to:
for ch in letter_map[digits[idx]]:
# add to our backtracking stack
# the new index, which is idx + 1, and the new current
# string, which is the string + the character we mapped to.
stack.append((idx + 1, string + ch))
return letter_combos