# Letter Combinations of a Phone Number

## Problem

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 digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

![](https://1063826111-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MGdx41c9p2PMgIHbUTK%2F-MNJrd2MzYp-_tmggAlc%2F-MNJuKuSdAMc5APT6-tI%2Fimage.png?alt=media\&token=f6013c38-34a7-448f-af87-851451c4628f)

{% hint style="info" %}
For example:

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

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

{% endhint %}

### Thought Process

![](https://1063826111-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MGdx41c9p2PMgIHbUTK%2F-MNJrd2MzYp-_tmggAlc%2F-MNJvnhygv-J0h1HCIyy%2FIMG_A6BA9B366BEE-1.jpeg?alt=media\&token=aa9a7c05-6a4f-409e-9e3e-15866ffd418f)

* *How can we map the letters to the numbers? With a dictionary?*

  * Yes. We can map each letter to it's corresponding numbers and in out for-loop we refernce the number key in the dictionary so we can loop through the letters. We **DO NOT** loop through the numbers

* We **DO NOT** loop through the numbers. We only loop through the **letters** of the numbers. To handle "looping" through the numbers, in our recursion method we just call on the next number in the input digit with digit\[1: ]. This retrieves the next digit and the for-loop will iterate through it's characters. 

## Solution

```
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if digits == "":
            return []
        
        letters = {
            "0":"0",
            "1":"1",
            "2":"abc",
            "3":"def",
            "4":"ghi",
            "5":"jkl",
            "6":"mno",
            "7":"pqrs",
            "8":"tuv",
            "9":"wxyz",
        }
        
        soln = []
        self.helper(digits, letters,"", soln)
        return soln
    
    def helper(self,digits,letters, comb, soln):
        if len(digits) == 0:
            soln.append(comb)
            return 
        
        chars = letters[digits[0]]
        
        for i in chars:
            comb+=i
            self.helper(digits[1:],letters,comb,soln)
            comb = comb[:-1]
        
```

## Key Points 

* We use a dictionary in order to map the letters to the numbers

* It is important you realize, again, we **DO NOT** loop through the numbers. We only loop through the **letters** which we retrieve from the dictionary with the number as key. 

## Time Complexity

* **Time:**$$O(n\* 4^n)$$ because at most there will be $$4^n$$forks (because of the letters in 7 and 9 on the phone) and it will be done *n* times for each number given (see the Thought Process picture above)

* **Space:** $$O(4^n)$$ is the most calls the recursion stack will use