loading

17. Letter Combinations of a Phone Number — Step-by-Step Visualization

mediumLeetCode #17BacktrackingString

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. ``` 1: "", 2: "abc", 3: "def" 4: "ghi", 5: "jkl", 6: "mno" 7: "pqrs", 8: "tuv", 9: "wxyz" ``` **Example 1:** Input: `digits = "23"` Output: `["ad","ae","af","bd","be","bf","cd","ce","cf"]` **Example 2:** Input: `digits = ""` Output: `[]` **Example 3:** Input: `digits = "2"` Output: `["a","b","c"]`

Algorithm Pattern

Backtracking

Key Idea

Build combinations exhaustively digit by digit, branching for each possible letter.

Step-by-Step Approach

  1. If the input string is empty, we return an empty array.
  2. Maintain a current combination string being built, starting empty.
  3. For each step, take the next digit from the input, loop through its corresponding characters.
  4. For each character, add it to the combination and recurse on the next digit.
  5. When the combination length equals the input string length, a full combination is found; add it to results.

Common Gotchas

  • Handling the case where digits is an empty string specifically.
  • Ensuring backtracking is properly layered so strings don't accumulate incorrectly.

Related Problems

← All problems