menu

[LeetCode] 017. Letter Combinations of a Phone Number

Problem (Medium)

017. 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) 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.

Approach 1: Recursive Append

Idea

Recursively check if the combination should be added to result.

  • If there’s no more digits to check, the current combination is done.
  • If there are still digits to check:
    • Iterate over the letters mapping the next available digit.
      • Append the current letter to the current combination combination = combination + letter.
      • Proceed to check next digits : recurse(combination + letter, next_digits[1:]).

Solution

class Solution1:
   def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        ret = []
        if digits:
            self.recurse(ret, '', digits)
        return  ret
 
    dic = {
        '2': 'abc',
        '3': 'def',
        '4': 'ghi',
        '5': 'jkl',
        '6': 'mno',
        '7': 'pqrs',
        '8': 'tuv',
        '9': 'wxyz',
    }
    def recurse(self, ret, combination, digits):
        if len(digits) == 0:
            ret.append(combination)
        else:
            for c in self.dic[digits[0]]:
                self.recurse(ret, combination + c, digits[1:])

Complexity

  • Time: $O(3^N\times 4^M)$ where $N$ is the number of digits that maps to 3 letters, and $M$ is the number of digits that maps to 4 letter.
  • Space: $O(3^N\times 4^M)$ since we have to keep $3^N\times 4^M$ solutions.



KF

Comments