https://leetcode.com/problems/letter-combinations-of-a-phone-number/

letter-combinations-of-a-phone-number.cpp

class Solution
{
public:
    vector<string> letterCombinations(string digits)
    {
        if (digits.empty()) return{};

        static vector<string>dict = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
        vector<string> output;
        CombineLetterDFS(digits, dict, "", output);
        return output;
    }

private:
    void CombineLetterDFS(const string& digits, const vector<string>& dict, string out, vector<string>& output)
    {
        if (digits.empty())
        { 
            output.emplace_back(out);
            return;
        }

        for (auto letter : dict[digits[0] - '0'])
        {
            CombineLetterDFS(string(digits.begin() + 1, digits.end()), dict, out + letter, output);
        }
    }
};

first version
Runtime 4 ms
Memory 9.2 MB

second version
Runtime 8 ms
Memory 8.7 MB