17_Letter Combinations of a Phone number

[Medium]

Given a string containing digits from2-9inclusive, 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. Note that 1 does not map to any letters.

Example:

Input: "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: (iterative)

Idea:

• Two passes. In the first pass, compute the length of the final output. In the second pass, append letters for each element.

• Use an index which is at the same length as the final output to indicate which letter should we write. Divide the product of the letter length of all the future digits, the quotient indicates the index of current letter, the modulo indicates index for next round.

Time Complexity: $O(4^n n)$ where n is the length of input.

Space Complexity: $O(4^n)$ where n is the length of input.

def letterCombinations(digits):
    """
    :type digits: str
    :rtype: List[str]
    """
    if digits == "": return []

    # mapping from digits to letters
    map = ["abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]

    # iterative approach
    # first pass to compute the length of final output
    n = 1
    for i in range(len(digits)):
        letters = map[int(digits[i])-2]
        n *= len(letters)

    out = [""]*n
    index = range(n)
    length = n

    # second pass to append letter
    for i in range(len(digits)):
        letters = map[int(digits[i])-2]
        length /= len(letters)
        for j in range(n):
            out[j] += letters[index[j]//length]
            index[j] %= length
    return out

Solution 2: recursive

Solution 3: using tree and depth first traverse of tree