Skip to content

17. Letter Combinations of a Phone Number

Difficulty Topics

Description

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

 

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = ""
Output: []

Example 3:

Input: digits = "2"
Output: ["a","b","c"]

 

Constraints:

  • 0 <= digits.length <= 4
  • digits[i] is a digit in the range ['2', '9'].

Solution

letter-combinations-of-a-phone-number.py
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits: return []

        mp = {2:"abc",3:"def",4:"ghi",5:"jkl",6:"mno",7:"pqrs",8:"tuv",9:"wxyz"}
        n = len(digits)
        res = []

        def go(index, curr):
            if index == n:
                res.append(curr)
                return

            for x in mp[int(digits[index])]:
                go(index + 1, curr + x)

        go(0, "")

        return res