Letter Combinations of a Phone Number

17. Letter Combinations of a Phone Number

Difficulty: Medium

Related Topics: Hash Table, String, Backtracking

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”]

Code:

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        res = []
        if not digits:
            return res
        hashmap = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz"
        }
        res = []
        
        def backtracking(ind, letter):
            nonlocal res
            if ind == len(digits):
                res.append(letter)
                return      ## Return to break out from recursion

            num = digits[ind]
            chars = hashmap[num]
            for i in chars:
                backtracking(ind+1, letter+i)
        
        backtracking(0, "")
        return res