17_Letter_Combinations_of_a_Phone_Number.md

17. Letter Combinations of a Phone Number

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 digit 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'].

def letterCombinations(self, digits: str) -> List[str]:
        result = []
        if digits == "":
            return result
        dic = {
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mno',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz'
        }
        
        def combine(build, index):
            
            if index == len(digits):
                result.append(build)
                return
            
            chars = dic[digits[index]]
            for c in chars:
                combine(build+c, index+1)
            
        combine("", 0)
        return result

Runtime: 28 ms, faster than 79.22% of Python3 online submissions for Letter Combinations of a Phone Number.
Memory Usage: 14.3 MB, less than 100.00% of Python3 online submissions for Letter Combinations of a Phone Number.