17. Letter Combinations of a Phone Number

tag: FB problem * 6

Given a digit string, 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.

Input:
Digit string "23"

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

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

Solution:

Time compelxity: O( $$3^n$$ ) because for each digit there's on average 3 options to choose from. Thus 3 * 3 * .. 3 for n times

Space Complexity: same as time complexity. because each valid combination takes 1. There are 3 ^n combinations

1. create a dictionary mapping from each single digit to a list of its letters
2. dfsVisit digit, with starting position specified by "pos" parameter. Because we have to choose at lease one letter from each position specified digit.
3. Be careful with edge case. If digits = "", that means there's no digit, thus we shouldn't append "" into final result

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        dic = self.createDictionary()

        res = []
        self.dfsVisit(digits, 0, "", res, dic)

        return res

    def dfsVisit(self, digits, pos, cur, res, dic):
        if pos == len(digits):
            if cur != "": # edge case, when 
                res.append(cur)
            return
        # Because we have to choose at lease one letter from each position specified digit.
        letters = dic[digits[pos]]
        for letter in letters:
            self.dfsVisit(digits, pos + 1, cur + letter, res, dic)


    def createDictionary(self):
        dic = {}

        dic["0"] = [" "]
        dic["1"] = [""]
        dic["2"] = ["a", "b", "c"]
        dic["3"] = ["d", "e", "f"]
        dic["4"] = ["g", "h", "i"]
        dic["5"] = ["j", "k", "l"]
        dic["6"] = ["m", "n", "o"]
        dic["7"] = ["p", "q", "r", "s"]
        dic["8"] = ["t", "u", "v"]
        dic["9"] = ["w", "x", "y", "z"]
        return dic