On an old phone keypad, each digit from 2 to 9 maps to a few letters (2 is "abc", 3 is "def", up to 9 which is "wxyz"). Given a string digits, return every letter string that the digits could spell, in any order. If digits is empty, return an empty list.
- 0 <= digits.length <= 4
- digits[i] is a digit in the range '2' to '9'
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Nested loops would work only if we knew the number of digits in advance. Backtracking gives us "a loop per digit" of any depth: at level i we try each letter of digits[i], then go one level deeper. Every leaf of this recursion tree is one complete word, and there are at most 4^n of them, so the work is proportional to the output size, which is the best we can do.
Algorithm
- If
digitsis empty, return[]. - Store the digit to letters mapping in an array or map.
- Define
backtrack(i, path). Ifi == len(digits), addpathto the result. - Otherwise, for each letter mapped to
digits[i], append it, recurse withi + 1, then remove it.
O(4^n * n)Space: O(n) recursion depth, excluding the output[""] instead of [] is the most common wrong answer.class Solution: def letterCombinations(self, digits: str) -> List[str]: if not digits: return [] keys = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"} res, path = [], []Β def backtrack(i): if i == len(digits): res.append("".join(path)) return for c in keys[digits[i]]: path.append(c) backtrack(i + 1) path.pop()Β backtrack(0) return res