solution to leetcode #0017

leetcode-0017.py

# Sarah Anoke
# sarah@sanoke.info
# solution to leetcode #0017
# https://leetcode.com/problems/letter-combinations-of-a-phone-number/

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')
# expected output:
# ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

Solution().letterCombinations('92')
# expected output:
# ['wa', 'wb', 'wc', 'xa', 'xb', 'xc', 'ya', 'yb', 'yc', 'za', 'zb', 'zc']