leetcode Question 42: Letter Combinations of a Phone Number

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