Medium

Letter Combinations of a Phone Number

080

Return all letter combinations for the given digit string using the phone keypad mapping.

EXAMPLES

Example 1

Input
{
  "digits": "23"
}

Output
[
  "ad",
  "ae",
  "af",
  "bd",
  "be",
  "bf",
  "cd",
  "ce",
  "cf"
]

FUNCTION SHAPE

digits: string→stringArray

SOLUTION NOTE

We apply the template. We need to construct a map from digit -> list of possible characters.

These represent our choices at some digit i, we can map to any of these characters.

Note: there is an edge case at the end: if digits = "", backtrack(0) returns [""] instead of [], so we need the last check.

Reveal reference solution +

pythonREFERENCE

def letterCombinations(self, digits: str) -> List[str]:
    keyPad = ["", "", "abc", "def", "ghi", "jkl", "mno", "qprs", "tuv", "wxyz"]

    res = []
    curr = []
    n = len(digits)

    def backtrack(i):
        if i == n:
            res.append(''.join(curr))
        else:
            for c in keyPad[int(digits[i])]:
                curr.append(c)
                backtrack(i+1)
                curr.pop()

    backtrack(0)
    return res if len(digits) > 0 else []

TimeO(4^n)

SpaceO(n)

Open on LeetCode ↗