17.Letter Combinations of a Phone Number

Tags: [recursion]

Com: {fb}

Link: https://leetcode.com/problems/letter-combinations-of-a-phone-number/\#/description

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: Recursion

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if not digits:
            return []

        mapping = {
            '0': [' '],
            '1': [],
            '2': list('abc'),
            '3': list('def'),
            '4': list('ghi'),
            '5': list('jkl'),
            '6': list('mno'),
            '7': list('pqrs'),
            '8': list('tuv'),
            '9': list('wxyz')
        }
        result = []
        buff = []
        self.letter_combinations_helper(digits, 0, buff, result, mapping)
        return result

    def letter_combinations_helper(self, digits, index, buff, result, mapping):
        # base case
        if index >= len(digits):
            result.append(''.join(buff))
            return

        for c in mapping.get(digits[index], []):
            buff.append(c)
            self.letter_combinations_helper(digits, index + 1, buff, result, mapping)
            buff.pop()

Note:

• Time complexity = O(4^n), n is the length of the given string, here the time complexity is O(4^n), because the '7' and '9' mapping to 4 characters, which is the worst case for the single level of the recursion.