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.

1
2
3
4
Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
1
2
3
4
Example 2:

Input: digits = "2"
Output: ["a","b","c"]
1
2
3
4
Constraints:

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

Approach

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from typing import List

class Solution:
    digits_map = {
        "2": "abc",
        "3": "def",
        "4": "ghi",
        "5": "jkl",
        "6": "mno",
        "7": "pqrs",
        "8": "tuv",
        "9": "wxyz",
    }

    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []

        result = [""]

        for digit in digits:
            temp = []
            for prefix in result:
                for ch in self.digits_map[digit]:
                    temp.append(prefix + ch)
            result = temp

        return result