Letter Combinations of a Phone Number
Medium· backtracking
Problem
On an old phone keypad, digits 2-9 each map to three or four letters. Given a string of such digits, return every letter string the digits could spell. Return an empty list for an empty input.
Examples
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Input: digits = "7"
Output: ["p","q","r","s"]
Constraints
- • 0 <= digits.length <= 4
- • Each digit is in the range 2-9
Hints & approach
Hint 1
Store the digit-to-letters mapping in a small table.
Hint 2
Recurse over digit positions, trying each letter for the current digit.
Approachtry the hints first
Recurse on the index into digits while building a string. At index i, loop over the letters mapped to digits[i], append one, recurse on i + 1, and remove it. When i equals the length, the built string is complete and goes into the result. With at most four letters per digit the output has up to 4^n strings, each of length n.
Time O(n * 4^n) · Space O(n) recursion, excluding output