class Solution
{
public:
	vector<string> letterCombinations(string digits)
	{
		vector<string> nummap({" ",
							   "",
							   "abc",
							   "def",
							   "ghi",
							   "jkl",
							   "mno",
							   "pqrs",
							   "tuv",
							   "wxyz"});
		vector<string> rs;
		vector<string> empty;
		if (digits.size() == 0)
			return empty;
		for (auto d : digits)
		{
			if (d == '0')
				return empty;
			if (d == '1')
				return empty;
			auto &s = nummap[d - '0'];
			if (s.size() == 0)
				continue;
			if (rs.size() == 0)
				for (auto c : s)
				{
					string t;
					t.push_back(c);
					rs.emplace_back(t);
				}
			else
			{
				vector<string> rn;
				for (auto c : s)
				{
					for (auto r : rs)
					{
						r.push_back(c);
						rn.emplace_back(std::move(r));
					}
				}
				std::swap(rs, rn);
			}
		}
		return rs;
	}
};