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.

Analysis:

This is a simple problem, we can use the DFS to solve it. Details see the source code.

Code(C++):

class Solution {
public:
void dfs(string digits, string r, map<char,vector<char> > &mp, vector<string> &res){
if (digits.empty()){
res.push_back(r);
}else{
vector<char> vec = mp[digits[0]];
for(int i=0;i<vec.size();i++){
dfs(digits.substr(1),r+vec[i],mp,res);
}
}
}
vector<string> letterCombinations(string digits) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
map<char,vector<char> > mp;
vector<char> v;
int n=2;
for (char i='a';i<='z';i++){
v.push_back(i);
if (i=='c' || i=='f'|| i=='i'|| i=='l'|| i=='o'|| i=='s'|| i=='v'|| i=='z'){
mp[char(n+'0')]=v;
n++;
v.clear();
}
}

vector<string> res;
dfs(digits,"",mp,res);
return res;
}
};


Code (Python):

class Solution(object):
def search(self, digits, k, s, res, mp):
if k == len(digits):
res.append(s)
else:
for d in mp[digits[k]]:
self.search(digits, k+1, s+d, res, mp)

def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
if digits == '':
return []
mp = {'1':[], '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'], '0':[]}
res = []
self.search(digits, 0, '', res, mp)
return res