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

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

Example:

Input: “23”

Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

Explanation: The answer is “abc”, with the length of 3.

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

Solution

from typing import List

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        def helper(curString: List[str], i: int) -> None:
            nonlocal digitLetterMap, combos

            if i == len(digits):
                combos.append("".join(curString))
                return

            for letter in digitLetterMap[int(digits[i])]:
                curString[i] = letter
                helper(curString, i+1)

        if not digits: return []
        digitLetterMap = ['0','1','abc','def','ghi','jkl','mno','pqrs','tuv','wxyz']
        combos = []
        helper([None]*len(digits), 0)
        return combos

Test Cases

test = Solution()
assert test.letterCombinations('23') == [
    "ad",
    "ae",
    "af",
    "bd",
    "be",
    "bf",
    "cd",
    "ce",
    "cf"
]
assert test.letterCombinations('') == []
print('All Passed!')

Big O Analysis

Space Complexity: O(4^N)

Time Complexity: O(4^N)