Medium · Cartesian Backtracking
Understand → Visualise → Practice.
Return all letter strings represented by digits 2 through 9 on a telephone keypad.
Each digit maps to 3 or 4 letters. Recurse through the digits, appending each possible letter for the current digit.
2 → abc, 3 → def, … 7 → pqrs, 9 → wxyz.
At digit i, append each of its letters and recurse to i + 1.
When every digit has a letter, save the string; empty input gives no strings.
O(n × 4ⁿ) time and O(n) recursion depth, plus the output.
Returning [""] for empty input is wrong here; the expected answer is an empty list.
Read the full guide first: Recursion and Backtracking.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.