Backtracking/Letter Combinations of a Phone NumberMedium

This practice workspace is built for desktop. Open it on a larger screen to start solving.

Letter Combinations of a Phone Number

Backtracking·Medium

Given a string digits containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent using the standard phone keypad mapping:

2 → abc, 3 → def, 4 → ghi, 5 → jkl
6 → mno, 7 → pqrs, 8 → tuv, 9 → wxyz

If digits is empty, return [].

Use backtracking: for each digit in turn, extend every current prefix with each of that digit's letters.

Return the combinations sorted in ascending lexicographic order.

Examples

Input: digits = "23"

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

2 maps to abc and 3 maps to def; all 9 combinations sorted.

Input: digits = ""

Output: []

Input: digits = "2"

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

Constraints

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

00:00Preview Mode (Read Only)

Loading editor…

Tests

Preview Mode

This is a read-only preview of DSAMind's AI coaching. Sign up to get custom feedback on your own solution.

Passed32 ms

First attempt — retry to track metric movement here.

Your approach

Pattern:Backtracking
Time:O(N)
Space:O(1)

Complete approach — pattern and complexity both named.

Coach

What you got right

You correctly matched the sorted input requirement and implemented a linear-time scan using two pointers.

Where it diverged

No divergence detected. The code correctly aligns with the stated approach.

Next attempt: focus on

Try solving related sliding window problems to build familiarity with two-pointer variants.

Signals

No signals fired — clean run, you stayed in flow.