# LeetCode: Letter Combinations of a Phone Number

By | 2012 年 9 月 29 日

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.

## Analyze

Process the digits one by one, for each digits, append the possible characters to the existing strings. For example, if input is “23”.

For digit `2`, the possible chars are `a, b, c`. So after this step we have a list of `['a', 'b', 'c']`

For digit `3`, the possible chars are `d, e, f`. So for each existing strings in the list, append each char to all of them. So for `d` we have `ad, bd, cd`, for `e` we have `ae, be, ce`; for `f` we have `af, bf, cf`. Combine them together, got the list of: `['ad', 'bd', 'cd', 'ae', 'be', 'ce', 'af', 'bf', 'cf']`

## Solutions

### Ruby

```MAP = {
'2' => 'abc',
'3' => 'def',
'4' => 'ghi',
'5' => 'jkl',
'6' => 'mno',
'7' => 'pqrs',
'8' => 'tuv',
'9' => 'wxyz'
}
# @param {String} digits
# @return {String[]}
def letter_combinations(digits)
results = [''] # add the seed
digits.each_char do |digit|
chars = MAP[digit]
results = results.map{|item| chars.each_char.map{|c| item + c} }.flatten
end
results.delete('') # delete the seed if still there
results
end
```

### C++

```class Solution {
public:
vector<string> letterCombinations(string digits) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<vector<char> >map(10);
map[0] = vector<char>(1);

map[0][0] = ' ';
map[1] = vector<char>(1);
map[1][0] = ' ';

map[2] = vector<char>(3);
map[2][0] = 'a';
map[2][1] = 'b';
map[2][2] = 'c';

map[3] = vector<char>(3);
map[3][0] = 'd';
map[3][1] = 'e';
map[3][2] = 'f';

map[4] = vector<char>(3);
map[4][0] = 'g';
map[4][1] = 'h';
map[4][2] = 'i';

map[5] = vector<char>(3);
map[5][0] = 'j';
map[5][1] = 'k';
map[5][2] = 'l';

map[6] = vector<char>(3);
map[6][0] = 'm';
map[6][1] = 'n';
map[6][2] = 'o';

map[7] = vector<char>(4);
map[7][0] = 'p';
map[7][1] = 'q';
map[7][2] = 'r';
map[7][3] = 's';

map[8] = vector<char>(3);
map[8][0] = 't';
map[8][1] = 'u';
map[8][2] = 'v';

map[9] = vector<char>(4);
map[9][0] = 'w';
map[9][1] = 'x';
map[9][2] = 'y';
map[9][3] = 'z';

vector<string> result;
result.push_back("");
for(int idigit = 0; idigit < digits.size(); ++ idigit) {
char di = digits[idigit];
int index = di - '0';
if(index < 0 || index > 9)
continue;
vector<char> &dmap = map[index];
int curSize = result.size();
int times = dmap.size();
for(int itime = 0; itime < times - 1; ++itime) {
for(int itemp = 0; itemp < curSize; ++itemp) {
result.push_back(result[itemp]);
}
}
for(int itime = 0; itime < times ; ++itime) {
char append = dmap[itime];
for(int itemp = 0; itemp < curSize; ++itemp) {
int itemIndex = itime * curSize + itemp;
if(itemIndex >= result.size()) {
cout<<"d";
continue;
}
result[itemIndex].push_back(append);
}
}
}
return result;
}
};
```