Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.

Example:

Input: "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.

code

#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
using namespace std;

class Solution
{
public:
    vector<string> letterCombinations(string digits)
    {
        vector<string> res;
        stringstream ss;
        int n;
        ss<<digits;
        ss>>n;
        if(digits.empty()||n<=0)
            return res;

        res.push_back("");
        int c=digits.size();
        vector<int> num{2,3,4,5,6,7,8,9};
        vector<string> str{"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

        while(n&&c>=0)
        {
            int h=n/(int)pow(10,c-1);
            n=n%(int)pow(10,c-1);
            --c;
            vector<int>::iterator it=find(num.begin(),num.end(),h);
            int dis=distance(num.begin(),it);

            const string &candidate=str.at(dis);
            if(candidate.empty())
                continue;
            vector<string> tmp;
            for(int i=0;i<res.size();++i)
            {
                for(int j=0;j<candidate.size();++j)
                    tmp.push_back(res.at(i)+candidate.at(j));
            }
            res.swap(tmp);
            vector<string> ().swap(tmp);
        }
        return res;
    }
};

int main()
{
    string str("22");
    Solution s;
    vector<string> res(s.letterCombinations(str));
    for(auto i:res)
        cout<<i<<" ";
    cout<<endl;
    return 0;
}