Letter Combinations of a Phone Number

#leetcode #python #backtracking #problemsolving

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.

class Solution(object):
    def letterCombinations(self, digits):

        res = []
        if not digits:
            return res

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

        def backtrack(i, curStr):
            if len(curStr) == len(digits):
                res.append(curStr)
                return

            for c in d[digits[i]]:
                backtrack(i + 1, curStr + c)


        backtrack(0, "")

        return res