Big-O analysis of two algorithms

Question

I created two solutions for leetcode problem 17 in which it asks you to generate all possible text strings from a phone number combination, e.g. "3" results in ["d","e","f"].

My first solution uses a recursive algorithm to generate the strings and is given below:

class Solution {
public:
    void fill_LUT(vector<string>& lut) {
        lut.clear();
        lut.push_back(" ");
        lut.push_back("");
        lut.push_back("abc");
        lut.push_back("def");
        lut.push_back("ghi");
        lut.push_back("jkl");
        lut.push_back("mno");
        lut.push_back("pqrs");
        lut.push_back("tuv");
        lut.push_back("wxyz");
    }

    void generate_strings(int index, string& digits, vector<string>& lut, vector<string>& r, string& work) {
        if(index >= digits.size()) {
            r.push_back(work);
            return;
        }

        char idx = digits[index] - '0';
        for(char c : lut[idx]) {
            work.push_back(c);
            generate_strings(index+1, digits, lut, r, work);
            work.pop_back();
        }
    }

    vector<string> letterCombinations(string digits) {
        vector<string> r;
        vector<string> lut;
        fill_LUT(lut);

        if(digits.size() <= 0)
            return r;

        string work;
        generate_strings(0, digits, lut, r, work);

        return r;
    }
};

I am a bit rusty with big-O, but it appears to me that the space complexity would be O(n) for the recursive call, i.e. its maximum depth, O(n) for the buffer string, and O(n*c^n) for the resulting strings. Would this sum together as O(n+n*c^n)?

For time complexity I am a bit confused. Each level of the recursion performs c pushes + pops + recursive calls multiplied by the number of operations by the next level, so it sounds like c^1 + c^2 + ... + c^n. In addition, there are c^n duplications of n length strings. How do I consolidate this into a nice big-O representation?

---

The second solution views the number of results as a mixed radix number and converts it to a string as you might perform an int to hex string conversion:

class Solution {
public:
    void fill_LUT(vector<string>& lut) {
        lut.clear();
        lut.push_back(" ");
        lut.push_back("");
        lut.push_back("abc");
        lut.push_back("def");
        lut.push_back("ghi");
        lut.push_back("jkl");
        lut.push_back("mno");
        lut.push_back("pqrs");
        lut.push_back("tuv");
        lut.push_back("wxyz");
    }

    vector<string> letterCombinations(string digits) {
        vector<string> r;
        vector<string> lut;
        fill_LUT(lut);

        if(digits.size() <= 0)
            return r;

        unsigned total = 1;
        for(int i = 0; i < digits.size(); i++) {
            digits[i] = digits[i]-'0';
            auto m = lut[digits[i]].size();
            if(m > 0) total *= m;
        }

        for(int i = 0; i < total; i++) {
            int current = i;
            r.push_back(string());
            string& s = r.back();
            for(char c : digits) {
                int radix = lut[c].size();
                if(radix != 0) {
                    s.push_back(lut[c][current % radix]);
                    current = current / radix;
                }
            }
        }

        return r;
    }
};

In this case, I believe that the space complexity is O(n*c^n) similar to the first solution minus the buffer and recursion, and the time complexity must be O(n) for the first for loop and an additional O(n*c^n) to create a result string for each of the possible results. The final big-O for this is O(n+n*c^n). Is my thought process correct?

---

Edit: To add some clarification to the code, imagine an input string of "234". The first recursive solution will call generate_strings with the arguments (0, "234", lut, r, work). lut is a look up table that converts a number to its corresponding characters. r is the vector containing the resulting strings. work is a buffer where the work is performed.

The first recursive call will then see that the index 0 digit is 2 which corresponds with "abc", push a to work, and then call generate_strings with the arguments (1, "234", lut, r, work). Once the call returns it will then push b to work and rinse and repeat.

When index is equal to the size of digits then a unique string has been generated and the string is pushed onto r.

---

For the second solution, the input string is first converted from it's ascii representation to it's integer representation. For example "234" is converted to "\x02\x03\x04". Then the code uses those as indices to look up the number of corresponding characters in the lookup table and calculates the total number of strings that will be in the result. e.g. if the input string was "234", 2 corresponds with abc, which has 3 characters. 3 corresponds with def which has 3 characters. 4 corresponds with ghi which has 3 characters. The total number of possible strings is 3*3*3 = 27.

Then the code uses a counter to represent each of the possible strings. If i were 15 it would be evaluated by first finding 15 % 3 which is 0, corresponding with the first character for the first digit (a). Then divide 15 by 3 which is 5. 5 % 3 is 2 which corresponds with the third character for the second digit, which is f. Finally divide 5 by 3 and you get 1. 1 % 3 is 1 which corresponds with the second character for the third digit, h. Therefore the string that corresponds with the number 15 is afh. This is performed for each number and the resulting strings are stored in r.

Answer 1

Recursive algorithm:

Space: each level of recursion is O(1) and there are O(n) levels. Thus it is O(n) for the recursion. The space of result is O(c^n), where c = max(lut[i].length). Total space for the algorithm is O(c^n).

Time: Let T(n) be the cost for digit with length n. Then we have recursion formula : T(n) <= c T(n-1) + O(1). Solve this equation give T(n) = O(c^n).

Hashing algorithm:

Space: if you need the space to store all results, then it is still O(c^n).

Time: O(n+c^n) = O(c^n).

---

I like the Hashing algorithm because it is better if the question asks you to give a specific string result (suppose we order them by alphabet order). In that case, the space and time is only O(n).

This question reminds me to a similar question: generate all permutations of the set {1,2,3,...,n}. The hashing approach is better because by generating the permutation one by one and process it, we can save a lot of space.