17. Letter Combinations of a Phone Number
Model: qwen3.5:9b
Topics: String,Backtracking,Depth-first Search,Recursion
FAANG asked: 1
Acceptance rate: 49.5%
Problem Breakdown
We are given a string of digits (2-9). We need to map each digit to its corresponding letters on a standard telephone keypad (e.g., ‘2’ -> “abc”, ‘3’ -> “def”). The goal is to generate every possible combination where the first letter comes from the set mapped by digits[0], the second from digits[1], and so on.
Inputs: A string of digits, length 0 to 4. Outputs: A list of strings representing all valid combinations. Order does not matter for correctness but typically sorted or lexicographical order is expected in practice (though problem says “any order”). Edge Cases:
- Empty Input (
""): The output must be an empty list[]. This often trips up recursive solutions if the base case isn’t checked before processing digits. - Single Digit: Should return all letters for that digit, not combinations with nothing else (handled naturally by recursion depth).
Intuition
This is a combinatorial problem where we need to form strings based on choices at each step.
- Brute Force Attempt: One might think of generating permutations or using nested loops. However, the number of digits isn’t fixed; it’s dynamic (up to length 4). Writing four levels of nesting is impossible because varies.
- Key Insight: This structure suggests a tree traversal where each level represents processing one digit from the input string. At any node in this recursion tree, we have multiple branches corresponding to the letters for that specific digit.
- Algorithm Choice: Depth-First Search (DFS) via Backtracking is ideal here. We build the current combination character by character. Once we’ve used all digits provided in the input, we have a complete valid string and add it to our results list.
Approach
- Define a mapping dictionary for digits ‘2’ through ‘9’. Note that ‘0’, ‘1’, or non-digits are not expected per constraints but good practice is robustness (though here strictly adhering to constraints).
- Initialize an empty list
resultto store combinations. - Create a recursive helper function, say
backtrack(index, current_path):- Base Case: If
index == len(digits), we have formed a complete string. Appendcurrent_pathtoresult. Return. - Recursive Step: Retrieve the letters associated with
digits[index]. Iterate through each letter:- Add the letter to
current_path. - Call
backtrack(index + 1, current_path).
- Add the letter to
- Base Case: If
- Handle the empty input case immediately before starting recursion to avoid unnecessary function calls or incorrect base cases (though checking inside handles it too).
Complexity Analysis
- Time Complexity: where is
digits.length.- There are at most 4 letters per digit. We generate a tree of depth . The number of leaf nodes (valid combinations) is roughly to .
- For each valid combination, we perform string operations proportional to the length (to append or join). Thus, total time scales with output size.
- Space Complexity: .
- The recursion stack depth is for auxiliary space.
- We must store all valid combinations in the result list, which takes proportional memory to the total number of characters generated (). If we consider only auxiliary space excluding output storage, it is .
Solution
class Solution:
def letterCombinations(self, digits: str):
# Handle empty input edge case immediately
if not digits:
return []
# Mapping for phone keypad letters
mapping = {
'2': "abc", '3': "def", '4': "ghi",
'5': "jkl", '6': "mno", '7': "pqrs",
'8': "tuv", '9': "wxyz"
}
result = []
def backtrack(index, current_path):
# Base case: if we've processed all digits in the input string
if index == len(digits):
result.append(current_path)
return
# Get letters for the current digit at 'index'
possible_letters = mapping[digits[index]]
# Iterate through each letter to branch out our combinations
for char in possible_letters:
backtrack(index + 1, current_path + char)
# Start recursion from index 0 with an empty path string
backtrack(0, "")
return result
Edge Cases Handled
- Empty String (
digits = ""): The function checksif not digits: return []at the start. This prevents entering recursion and returning a list containing one empty string (which would be incorrect). - Single Digit: Recursion depth is 1, base case triggers immediately after first iteration loop completes for that digit’s letters. Returns correct single-letter strings in a list.
- Max Length (
digits.length = 4): The recursion handles dynamic length without fixed nesting levels. Time complexity remains bounded by the output size generated at this depth.