letter_combinations_of_a_phone_number.py

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

"""

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if digits == "":
            return []
        
        ans = []
        sol = []

        letter_map = {'2' : "abc", '3' : "def", '4' : "ghi", '5' : "jkl", '6' : "mno",
                    '7' : "pqrs", '8' : "tuv", '9' : "wxyz"}
        n = len(digits)
        def dfs(index = 0):
            if index == n:
                ans.append(''.join(sol.copy()))
                return
            for each_letter in letter_map[digits[index]]:
                sol.append(each_letter)
                dfs(index + 1)
                sol.pop()
        
        dfs(0)

        return ans