:orphan:

Letter Combinations of a Phone Number
=====================================

.. highlight:: none

Problem
-------
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. Return the
answer in **any order**.

A mapping of digits to letters (just like on the telephone buttons) is
given below. Note that 1 does not map to any letters.

|image1|

 

**Example 1:**

::


   Input: digits = "23"
   Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

**Example 2:**

::


   Input: digits = "2"
   Output: ["a","b","c"]

 

**Constraints:**

- ``1 <= digits.length <= 4``
- ``digits[i]`` is a digit in the range ``['2', '9']``.

.. |image1| image:: https://assets.leetcode.com/uploads/2022/03/15/1200px-telephone-keypad2svg.png

.. highlight:: python

Pattern
-------
Hash Table, String, Backtracking

Solution
--------
First map each digit to a group of letters. We can generate letter combinations
by appending each letter in the group to each combination.

Code
----

.. literalinclude:: ../problems/medium/letter-combinations-of-a-phone-number/letter_combinations_of_a_phone_number__approach_1.py
    :language: python
    :lines: 11-

Test
----
>>> from letter_combinations_of_a_phone_number__approach_1 import letterCombinations
>>> letterCombinations('23')
['ad', 'bd', 'cd', 'ae', 'be', 'ce', 'af', 'bf', 'cf']
>>> letterCombinations('')
[]
>>> letterCombinations('2')
['a', 'b', 'c']

Complexity
----------
| :math:`n` is the length of ``digits``.
| Time: :math:`O(4^n)` — at each step, we append 4 letters to each combination
| Auxiliary Space: :math:`O(1)`

.. autofunction:: letter_combinations_of_a_phone_number__approach_1.letterCombinations