**source:**https://leetcode.com/problems/letter-combinations-of-a-phone-number/**C/C++**

**Solution to LeetCode**problem

**17**.

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

## Examples

**Example 1:**

Input:digits = “23”

Output:[“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]

**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

Using Dynamic Programming,

- We will grow a string starting with the first letter of the first digit of the phone number,
- For every letter available for the digit, we recursively call our helper method, growing the string.
- Once the string has the same length than the phone number, we add that string to the result.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
private:
unordered_map<char, string> letters;
vector<string> result;
string *num;
void generateStrings(string currentStr, int index) {
if (currentStr.size() == num->size())
result.push_back(currentStr);
for (int i=0; i<letters[(*num)[index]].size(); i++)
generateStrings(currentStr + letters[(*num)[index]][i], index + 1);
}
public:
vector<string> letterCombinations(string digits) {
if (digits.size() == 0)
return {};
num = &digits;
letters['2'] = "abc";
letters['3'] = "def";
letters['4'] = "ghi";
letters['5'] = "jkl";
letters['6'] = "mno";
letters['7'] = "pqrs";
letters['8'] = "tuv";
letters['9'] = "wxyz";
generateStrings("", 0);
return result;
}
};