Follow

# .css-ecb9sr{display:-webkit-box;display:-webkit-flex;display:-ms-flexbox;display:flex;-webkit-flex-direction:row;-ms-flex-direction:row;flex-direction:row;-webkit-align-items:center;-webkit-box-align:center;-ms-flex-align:center;align-items:center;width:16rem;}  Follow # 17. Letter Combinations of a Phone Number

## An example of a recursive algorithm

Nhut Nguyen
·Jan 2, 2023·

### Problem statement

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. #### Example 1

``````Input: digits = "23"
``````

#### Example 2

``````Input: digits = ""
Output: []
``````

#### Example 3

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

#### Constraints

• `0 <= digits.length <= 4`.

• `digits[i]` is a digit in the range `['2', '9']`.

### Solution: Recursive

If you know the combinations `result` of a string `digits`, what is the result of extending it one more digit?

Answer: The new result is constructed by adding each letter of the mapping of the new digit to each string of the `result`.

#### Example 1 and 3

Assume you have computed the result of `digits = "2"`, which is `["a","b","c"]`.

To compute the result of `digits = "23"`, you add each letter of the mapping `'3' -> {'d', 'e', 'f'}` to each string `"a", "b", "c"`.

You get the new result `["ad","ae","af","bd","be","bf","cd","ce","cf"]`.

#### Code

``````#include <vector>
#include <iostream>
#include <unordered_map>
using namespace std;
void combination(string& digits, unordered_map<char, vector<char> >& m,
int i, vector<string>& result) {
if (i >= digits.length()) {
return;
}
if (result.empty()) {
result = {""};
}
vector<string> newResult;
for (string& s : result) {
for (auto c : m[digits[i]]) {
newResult.push_back(s + c);
}
}
result.swap(newResult);
combination(digits, m, i + 1, result);
}
vector<string> letterCombinations(string digits) {
unordered_map<char, vector<char> > m{{'2', {'a', 'b', 'c'}},
{'3', {'d', 'e', 'f'}},
{'4', {'g', 'h', 'i'}},
{'5', {'j', 'k', 'l'}},
{'6', {'m', 'n', 'o'}},
{'7', {'p', 'q', 'r', 's'}},
{'8', {'t', 'u', 'v'}},
{'9', {'w', 'x', 'y', 'z'}}};
vector<string> result;
combination(digits, m, 0, result);
return result;
}
void printResult(vector<string>& result) {
cout << "[";
for (string& s : result) {
cout << s << ",";
}
cout << "]\n";
}
int main() {
vector<string> result = letterCombinations("23");
printResult(result);
result = letterCombinations("");
printResult(result);
result = letterCombinations("2");
printResult(result);
}
``````
``````Output:
[]
[a,b,c,]
``````

#### Complexity

• Runtime: `O(3^N)`, where `N = digits.length`. In this problem, `N` is very small (`N <= 4`).

• Extra space: `O(1)` (the small map).

### Implementation notes

You can use the assignment operator `'='` for `result.swap(newResult)`, i.e. `result = newResult`.

But this assignment allocates additional memory for a copy of `newResult` before assigning it to `result`.

The `std::swap()` algorithm avoids such copying by using `std::move()`. It exchanges the contents of each other without allocating additional memory.

### References

Thanks for reading. Feel free to share your thought about my content and check out my FREE book “10 Classic Coding Challenges”.