学步园

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.

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int n=digits.length();
        vector<string> ans;
        string tmp;
        vector<string> trans;
        trans.push_back(string(" "));
        trans.push_back(string(""));
        trans.push_back(string("abc"));
        trans.push_back(string("def"));
        trans.push_back(string("ghi"));
        trans.push_back(string("jkl"));
        trans.push_back(string("mno"));
        trans.push_back(string("pqrs"));
        trans.push_back(string("tuv"));
        trans.push_back(string("wxyz"));
        solve(ans,trans,tmp,digits,0,n);
        return ans;
    }
    void solve(vector<string>& ans,vector<string>& trans,string& tmp,string& digits,int k,int n)
    {
        if ( k==n )
        {
            ans.push_back(tmp);
            return;
        }
        int p=digits[k]-'0';
        int sz=trans[ p ].length();
        for(int i=0;i<sz;i++)
        {
            tmp.push_back(trans[p][i]);
            solve(ans,trans,tmp,digits,k+1,n);
            tmp.pop_back();
        }
    }
};