Blog

Leetcode #0017

Question Prompt

from https://leetcode.com/problems/letter-combinations-of-a-phone-number/

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit-to-letters (just like on the telephone buttons depicted on the right) 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

Let's write code to solve a specific example, then generalize it and put it into a function.

telephone = {
    2 : 'abc',
    3 : 'def',
    4 : 'ghi',
    5 : 'jkl',
    6 : 'mno',
    7 : 'pqrs',
    8 : 'tuv',
    9 : 'wxyz'
}
strCombos = []

I'll be using the backtracking (aka backtracing) approach here, an algorithm is very similar to the depth-first search algorithm used to traverse graphs. Backtracking is an algorithm to explore the entire solution space; when a candidate solution is determined to be invalid, it's discarded and we take a step backwards and change direction (i.e., make a different decision). In this case, we're backtracking with no constraint.

Our approach will be recursive. Our function backtrace(strCombo, remDigits) will take two arguments, the current string stem strCombo and the remaining digits remDigits. The function will

1. select out the next digit from remDigits, and its associated letter mapping.
2. for every letter j in that mapping, call bactrace() on strCombo + j and the remaining digits remDigits[1:].
3. the base case will be when remDigits is empty; at that point the current solution is complete and can be appended to the ongoing list of solutions, strCombos (defined outside of the function).

def backtrace(strCombo, remDigits):
    """
    :type strCombo: str
    :type remDigits: str
    :rtype: List[str]
    """

    # base case
    if not remDigits:
        # if there are no more digits,
        # append to the list of string combinations
        # and exit
        strCombos.append(strCombo)
        return True

    else:
        # otherwise, identify letters associated
        # with current digit and continue on to the next
        digit = int(remDigits[0])
        for j in telephone[digit]:
            print('appending ' + j + ' to ' + strCombo)
            print('running solutions for remaining digits ' + \
                  str(remDigits[1:]))
            backtrace(strCombo + j, remDigits[1:])

Let's now test the function and check its output.

backtrace('', '23')

    appending a to
    running solutions for remaining digits 3
    appending d to a
    running solutions for remaining digits
    appending e to a
    running solutions for remaining digits
    appending f to a
    running solutions for remaining digits
    appending b to
    running solutions for remaining digits 3
    appending d to b
    running solutions for remaining digits
    appending e to b
    running solutions for remaining digits
    appending f to b
    running solutions for remaining digits
    appending c to
    running solutions for remaining digits 3
    appending d to c
    running solutions for remaining digits
    appending e to c
    running solutions for remaining digits
    appending f to c
    running solutions for remaining digits

strCombos

['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

🎉 🎉 🎉 Great! Now that we have something that seems to work, let's remove the print() statements and enclose our code in our definition of the Solution class.

This code is also available within a GitHub Gist.

class Solution:
    def __init__(self):

        self.telephone = {
            2 : 'abc',
            3 : 'def',
            4 : 'ghi',
            5 : 'jkl',
            6 : 'mno',
            7 : 'pqrs',
            8 : 'tuv',
            9 : 'wxyz'
        }

    def letterCombinations(self, digits):

        def backtrace(strCombo, remDigits):
            # base case
            if not remDigits:
                # if there are no more digits,
                # append to the list of string combinations
                # and exit
                strCombos.append(strCombo)
                return True

            else:
                # otherwise, identify letters associated
                # with current digit and continue on to the next
                digit = int(remDigits[0])
                for j in telephone[digit]:
                    backtrace(strCombo + j, remDigits[1:])

        strCombos = []

        if digits:
            backtrace('', digits)

        return strCombos

Solution().letterCombinations('23')

['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

Solution().letterCombinations('92')

['wa', 'wb', 'wc', 'xa', 'xb', 'xc', 'ya', 'yb', 'yc', 'za', 'zb', 'zc']

---