# 17 Letter Combinations of a Phone Number

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.

![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/73/Telephone-keypad2.svg/200px-Telephone-keypad2.svg.png)

```
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.

**The Idea:** First map each digit to its cooresponding alphabet. Begin with the characters to the first digit.

```
e.g. if d = 2
s = {"a", "b", "c"}
```

Next, recursively build upon this string by copying each `s[i]` and appending each character cooresponding to the next digit.

```
prev = {"a", "b", "c"}
         |
next = {"ad", "ae", "af"}


prev = {"a", "b", "c"}
              |
next = {"bd", "be", "bf"}


prev = {"a", "b", "c"}
                   |
next = {"cd", "ce", "cf"}
```

**Complexity:** O(4^n) time and O(4^n) space

```cpp
const unordered_map<char, string> num_char =
    { { '2',"abc" },{ '3',"def" },
    { '4',"ghi" },{ '5',"jkl" },
    { '6',"mno" },{ '7',"pqrs" },
    { '8',"tuv" },{ '9',"wxyz" } };

void _letterCombinations(const string &digits, int iter, vector<string> &prev) {
    if (iter < digits.size()) {

        vector<string> next;
        const string target = num_char.at(digits[iter]);
        next.reserve(prev.size() * target.size());

        for (int i = 0; i < prev.size(); i++) {
            string build_upon = prev.at(i);
            for (int j = 0; j < target.size(); j++) {
                string next_str = build_upon + target.at(j);
                next.push_back(next_str);
            }
        }

        prev = next;
        _letterCombinations(digits, iter + 1, prev);
    }
}

string filter_digits(const string &digits) {
    string filtered;
    filtered.reserve(digits.size());
    for (char c : digits)
        if (c - '0' > 1)
            filtered.push_back(c);
    return filtered;
}

vector<string> letterCombinations(string digits) {
    digits = filter_digits(digits);
    if (digits.empty()) return vector<string>();

    vector<string> result;
    for (char c : num_char.at(digits[0])) {
        result.push_back(string(1, c));
    }

    _letterCombinations(digits, 1, result);
    return result;
}
```

**Python Solution 1**

This is actually a more efficient solution because I rather than completely rewriting over `prev` in the previous implementation, I pass in the updated seed (which is `next`), and return it in the end.

```python
class Solution:
    num_char = {'2': "abc", '3': "def", '4': "ghi",
                '5': "jkl", '6': "mno", '7': "pqrs",
                '8': "tuv", '9': "wxyz"}

    def __letter_combinations(self, digits, index, seed):
        """
        :type digits: str
        :type iter int
        :type seed List[str]
        :rtype: void
        """
        if index < len(digits):
            target = self.num_char[digits[index]]
            next = [prev + char for prev in seed for char in target]
            return self.__letter_combinations(digits, index + 1, next)
        else:
            return seed

    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """

        digits = ''.join(digit for digit in digits if int(digit) > 1)
        if not digits:
            return []

        seed = [char for char in self.num_char[digits[0]]]
        return self.__letter_combinations(digits, 1, seed)


#testing
obj = Solution()
result = obj.letterCombinations("239")
print(result)
```

**Python Solution 2**

Incrementally build off the base case, and just keep adding to it.

```python
num_char = {'2': "abc", '3': "def", '4': "ghi",
            '5': "jkl", '6': "mno", '7': "pqrs",
            '8': "tuv", '9': "wxyz"}

class Solution:
    def _letterCombinations(self, current, digit):
        new_current = []
        for comb in current:
            for char in num_char[digit]:
                new_current.append(comb+char)
        return new_current


    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """

        if not digits: return []
        current = [char for char in num_char[digits[0]]]
        if len(digits) == 1: return current

        for digit in digits[1:]:
            current = self._letterCombinations(current, digit)

        return current
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/17-letter-combinations-of-a-phone-number.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.