Letter Combinations of a Phone Number - Practice Coding Problems

Letter Combinations of a Phone Number - Problem

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.

Digit Mapping:

2: ABC
3: DEF
4: GHI
5: JKL
6: MNO
7: PQRS
8: TUV
9: WXYZ

Input & Output

Example 1 — Two Digits

$ Input: digits = "23"

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

💡 Note: Digit 2 maps to 'abc', digit 3 maps to 'def'. Each letter from 2 combined with each letter from 3 gives 3×3=9 combinations.

Example 2 — Empty Input

$ Input: digits = ""

› Output: []

💡 Note: Empty input string returns empty array as no digits to process.

Example 3 — Single Digit

$ Input: digits = "2"

› Output: ["a","b","c"]

💡 Note: Single digit 2 maps to letters 'a', 'b', 'c', so return each letter as separate combination.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

String of digits 2-9, each mapping to letters

Mapping

Each digit maps to 3-4 letters like phone keypad

Combinations

Generate all possible letter combinations

Output

Array of all valid combinations

Key Takeaway

🎯 Key Insight: Each digit choice creates multiple branches - systematically explore all combinations using backtracking or iterative building

Asked in

M Meta 45 a Amazon 38 G Google 32 M Microsoft 28

The key insight is to systematically generate all possible combinations by either building them iteratively or using recursive backtracking. The backtracking approach is more memory efficient as it builds one path at a time. Time: O(4^n), Space: O(n) for backtracking.

Common Approaches

Approach	Time	Space	Notes
✓ Backtracking - Recursive Exploration	O(4^n)	O(n)	Use recursive backtracking to build combinations character by character
Brute Force - Iterative Generation	O(4^n)	O(4^n)	Generate all combinations using nested loops and string concatenation

Backtracking - Recursive Exploration — Algorithm Steps

Define recursive function with current combination and digit index
Base case: when all digits processed, add combination to result
For current digit, try each possible letter
Recurse with updated combination and next digit index

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin with empty combination at root

First Level

Branch for each letter of first digit

Second Level

Branch further for second digit letters

Collect

Collect all complete paths as results

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char** result;
int resultSize;
int resultCapacity;
char* phone[] = {
    "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};

void backtrack(char* digits, int index, char* current, int currentLen) {
    if (index == strlen(digits)) {
        if (resultSize >= resultCapacity) {
            resultCapacity *= 2;
            result = realloc(result, resultCapacity * sizeof(char*));
        }
        result[resultSize] = malloc((currentLen + 1) * sizeof(char));
        strcpy(result[resultSize], current);
        resultSize++;
        return;
    }
    
    char* letters = phone[digits[index] - '0'];
    for (int i = 0; i < strlen(letters); i++) {
        current[currentLen] = letters[i];
        current[currentLen + 1] = '\0';
        backtrack(digits, index + 1, current, currentLen + 1);
    }
}

char** solution(char* digits, int* returnSize) {
    resultSize = 0;
    resultCapacity = 100;
    result = malloc(resultCapacity * sizeof(char*));
    
    if (!digits || strlen(digits) == 0) {
        *returnSize = 0;
        return result;
    }
    
    char current[10];
    current[0] = '\0';
    backtrack(digits, 0, current, 0);
    
    *returnSize = resultSize;
    return result;
}

int main() {
    char digits[10];
    fgets(digits, sizeof(digits), stdin);
    digits[strcspn(digits, "\n")] = 0;
    
    int returnSize;
    char** result = solution(digits, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("\"%s\"", result[i]);
        if (i < returnSize - 1) printf(",");
        free(result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(4^n)

Each digit can map to up to 4 letters, generating all combinations

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth equals input length, plus result storage

⚡ Linearithmic Space

68.0K Views

High Frequency

~15 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Backtracking - Recursive Exploration — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler