< Back





17. Letter Combinations of a Phone Number

We're given a string, digits, containing a phone number. We're asked to return all possible letter
combinations that the number could represent if typed into a phone. To solve this, we use
backtracking to create all possible combinations.

First things first, we create a mapping of digits to letters - this will help us lookup the letters
in constant time for a particular digit. Then, we backtrack like always - if the length of our
combination is equal to the size of the digits, we append the combination to the answer list.
For each character mapped to our current digit, denoted by index i that we maintain, we append the
character to the combination and recursively call the backtrack function for the next digit to
handle, incrementing the index by 1. Once the recursion is done, we pop the character from the
working combination and move to the next one.

The solution is as follows:


  class Solution:
      def letterCombinations(self, digits: str) -> List[str]:
          mapping = {
              "2": "abc",
              "3": "def",
              "4": "ghi",
              "5": "jkl",
              "6": "mno",
              "7": "pqrs",
              "8": "tuv",
              "9": "wxyz",
          }

          n, ans = len(digits), []

          if not n:
              return ans

          def backtrack(s: List[str], i: int) -> None:
              if i == n:
                  ans.append("".join(s))
                  return

              for c in mapping[digits[i]]:
                  s.append(c)
                  backtrack(s, i + 1)
                  s.pop()

          backtrack([], 0)

          return ans


_ Time Complexity:

  O(n * 4^n) - We have 4 possible characters for each digit, and we have n digits. Also, joining the
  combination to append to the answer list takes O(n) time.

_ Space Complexity:

  O(n) - The recursion stack will have at most n frames.