class Solution {

public:

    void dfs(string temp,vector<string>&ret,string digits,int index,string* str,int len)

    {

        if(index==len)

        {

            ret.push_back(temp);

            return;

        }

        else

        {

            int n=str[(digits[index]-'2')].length();

            for(int i=0;i<n;i++)

            dfs((temp+str[(digits[index]-'2')][i]),ret,digits,index+1,str,len);

        }

    }

public:

    vector<string> letterCombinations(string digits) {

        vector<string>ret;

        if(digits=="")

            return ret;

        string str[10] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

        int len=digits.length();

        string temp="";

        this->dfs(temp,ret,digits,0,str,len);

        return ret;

    }

};