class Solution {
private:
    void recur(string s,unordered_map<char,string> &ump,
               vector<string> &ans,string str,int u){
        if(s.size() == 0 && str.size() == u){
            ans.push_back(str);
            return;
        }
        for(int i=0;i<s.size();i++){
            string t = ump[s[i]];
            for(int j=0;j<t.size();j++){
                str.push_back(t[j]);
                recur(s.substr(i+1,s.size()-1),ump,ans,
str,u);
                str.pop_back();
            }
        }
    }
public:
    vector<string> letterCombinations(string digits) {
        unordered_map<char,string> ump;
        ump['2'] = "abc";ump['3']="def";ump['4']="ghi";
        ump['5']="jkl";
        ump['6']="mno";ump['7']="pqrs";ump['8']="tuv";
        ump['9']="wxyz";
        vector<string> ans;
        string str;int u = digits.size();
        if(u == 0)
            return ans;
        recur(digits,ump,ans,str,u);
        return ans;
    }
};