## (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.

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.

Thoughts:
Another classic recursion problem. We try to generate solution each time by iterating through every digit and every character that digit maps to. If we overflow, we cut that solution and stop. If we get the correct solution (where solution.length() == digits.length()), we add to the solution set.

Code (Java):

```public class Solution {
private HashMap<Character, String> map;

public ArrayList<String> letterCombinations(String digits) {
setup();
ArrayList<String> solutions
= new ArrayList<String>();
recursion(digits, 0, new String(), solutions);
return solutions;
}

private void recursion(String digits, int start,
String sol, ArrayList<String> solutions) {
if(sol.length() > digits.length()) {
return;
} else if(sol.length() == digits.length()) {
return;
} else {
for(int i = start; i < digits.length(); ++i) {
String letters = map.get(digits.charAt(i));
for(int j = 0; j < letters.length(); ++j) {
recursion(digits, i + 1, sol + letters.charAt(j), solutions);
}
}
}
}

private void setup() {
map = new HashMap<Character, String>();
map.put('1', "");
map.put('2', "abc");
map.put('3', "def");
map.put('4', "ghi");
map.put('5', "jkl");
map.put('6', "mno");
map.put('7', "pqrs");
map.put('8', "tuv");
map.put('9', "wxyz");
map.put('0', " ");
}
}

Code (C++):
class Solution {
public:
vector<string> letterCombinations(string digits) {
setup();
vector<string> solutions;
string s;
recursion(digits, 0, s, solutions);
return solutions;
}

private:
map<char, string> mapping;
void recursion(string digits, int start,
string sol, vector<string>& solutions) {
if(sol.size() > digits.size()) {
return;
} else if(sol.size() == digits.size()) {
solutions.push_back(sol);
return;
} else {
for(int i = start; i < digits.size(); ++i) {
string letters = mapping[digits[i]];
for(int j = 0; j < letters.size(); ++j) {
recursion(digits, i + 1, sol + letters[j], solutions);
}
}
}
}

void setup() {
mapping.clear();
mapping['1'] = "";
mapping['2'] = "abc";
mapping['3'] = "def";
mapping['4'] = "ghi";
mapping['5'] = "jkl";
mapping['6'] = "mno";
mapping['7'] = "pqrs";
mapping['8'] = "tuv";
mapping['9'] = "wxyz";
mapping['0'] = " ";
}
};

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5b2deaa80475c', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5b2deaa80478a',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5b2deaa80478c',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});