lintcode-电话号码的字母组合-425

给一个数字字符串，每个数字代表一个字母，请返回其所有可能的字母组合。

下图的手机按键图，就表示了每个数字可以代表的字母。

Cellphone

样例

给定 "23"

返回 ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

class Solution {
public:
    void init(){
        node['2'].push_back('a');
        node['2'].push_back('b');
        node['2'].push_back('c');
    
        node['3'].push_back('d');
        node['3'].push_back('e');
        node['3'].push_back('f');
        
        node['4'].push_back('g');
        node['4'].push_back('h');
        node['4'].push_back('i');
        
        node['5'].push_back('j');
        node['5'].push_back('k');
        node['5'].push_back('l');
        
        node['6'].push_back('m');
        node['6'].push_back('n');
        node['6'].push_back('o');
        
        node['7'].push_back('p');
        node['7'].push_back('q');
        node['7'].push_back('r');
        node['7'].push_back('s');
        
        node['8'].push_back('t');
        node['8'].push_back('u');
        node['8'].push_back('v');
        
        node['9'].push_back('w');
        node['9'].push_back('x');
        node['9'].push_back('y');
        node['9'].push_back('z');
    }
    void letterCombinations(const string &s,int length,int pos){
        if(pos==length){
            ret.push_back(base);
            return ;    
        }
        vector<char> &tmp=node[s[pos]];
        int size=tmp.size();
        for(int i=0;i<size;++i){
            base.push_back(tmp[i]);
            letterCombinations(s,length,pos+1);              
            base.pop_back();
        }
    }
    vector<string> letterCombinations(string& digits) {
        if(digits.empty())
            return ret;
        init();
        letterCombinations(digits,digits.length(),0);
        return ret;
    }
private :
    vector<string> ret;
    string base;
    map<char,vector<char> > node;
};