DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Letter Combinations of a Phone Number

mediumRecursion

Problem statement

On a classic phone keypad, each digit from 2 to 9 stands for a few letters:

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

Given a string of digits from 2 to 9, return every string you could spell by choosing one letter for each digit, in order. The result can be in any order. If the input is empty, return an empty list.

Examples

Example 1

Input: digits = "46"

Output: ["gm", "gn", "go", "hm", "hn", "ho", "im", "in", "io"]

Explanation: 3 letters for 4 times 3 letters for 6 gives 9 strings.

Example 2

Input: digits = "9"

Output: ["w", "x", "y", "z"]

Hints

Approach

Backtracking builds one string at a time in a single buffer and records it when it is complete.

  1. If digits is empty, return [].
  2. dfs(i): if i == len(digits), record the buffer as a string.
  3. Otherwise, for each letter of digits[i], append it, call dfs(i + 1), and remove it.

The number of results is the same, so the time is the same, but the only extra memory beyond the output is the buffer and the recursion stack, both of length n. This is also the version that extends cleanly if you need to stop early, for example to keep only strings that are real words.

ComplexityTime O(4^n · n)Space O(n) besides the output
Python
KEYPAD = {
"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
"6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz",
}
class Solution:
def letterCombinations(self, digits: str) -> list[str]:
if not digits:
return []
result, path = [], []
def dfs(i: int) -> None:
if i == len(digits):
result.append("".join(path))
return
for ch in KEYPAD[digits[i]]:
path.append(ch)
dfs(i + 1)
path.pop()
dfs(0)
return result

Follow-up questions

  • Expand a hostname pattern such as db-{east,west}-{01,02} into every concrete name.
  • Return the combinations lazily with a generator so the full list is never held in memory.

Frequently asked questions

Big O uses the worst case. Digits 7 and 9 have four letters, so a string of only those digits produces 4^n results, each of length n.

The iterative version starts from [""], so without the early return it would hand back one empty string. The expected answer for no digits is no combinations, so check for it first.

Expanding a pattern into every concrete value is common: turning web-{a,b}-{1,2,3} into hostnames, generating a CI build matrix from lists of OS and runtime versions, or listing every region and zone pair. It is the same product-of-choices recursion.