I created two solutions for the leetcode 17 problem , in which he asks you to generate all possible text strings from a combination of phone numbers, for example. "3" results in ["d","e","f"] .
My first solution uses a recursive algorithm to generate 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'm a little rusty with big-O, but it seems to me that the spatial complexity will be O(n) for the recursive call, that is, its maximum depth, O(n) for the buffer line and O(n*c^n) for the resulting lines. Will this sum together be O(n+n*c^n) ?
For time complexity, I'm a little confused. Each recursion level performs c pushes + pops + recursive calls multiplied by the number of operations in the next level, so this is like c^1 + c^2 + ... + c^n . In addition, there is c^n duplication of strings of length n . How can I consolidate this into a nice big-O view?
The second solution considers the number of results as a mixed number of bases and converts it to a string, since you can convert int to a hexadecimal string:
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 complexity of the space O(n*c^n) similar to the first solution minus the buffer and recursion, and the time complexity should be O(n) for the first cycle of the cycle and additional O(n*c^n) to create a result line for each of the possible results. The final big-O for this is O(n+n*c^n) . Is my thinking process working correctly?
Edit: To add some explanation to the code, imagine the input string "234" . The first recursive solution will call generate_strings with arguments (0, "234", lut, r, work) . lut is a lookup table that converts a number to the corresponding characters. r is a vector containing the resulting rows. work is the buffer in which work is performed.
The first recursive call will see that index 0 is 2 , which corresponds to "abc" , press a in work , and then call generate_strings with arguments (1, "234", lut, r, work) . As soon as the call returns, it will then move b to work and flush and repeat.
When index is equal to the size of digits , then a unique row is generated and the row is placed on r .
For the second solution, the input string is first converted from it in the form of an ascii representation of an integer representation. For example, "234" converted to "\x02\x03\x04" . The code then uses them as indexes to find the number of matching characters in the lookup table and calculates the total number of rows that will result. for example, if the input string is "234" , 2 matches abc , which has 3 characters. 3 matches def , which has 3 characters. 4 corresponds to ghi , which has 3 characters. The total number of possible lines is 3*3*3 = 27 .
The code then uses a counter to represent each of the possible lines. If i were 15 , this would be evaluated first by finding 15 % 3 , which is 0 , corresponding to the first character for the first digit ( a ). Then divide 15 by 3 , which is 5 . 5 % 3 2 , which corresponds to the third character for the second digit, which is equal to f . Finally divide 5 by 3 and you get 1 . 1 % 3 1 , which corresponds to the second character for the third digit h . Therefore, the line corresponding to number 15 is afh . This is done for each number, and the resulting rows are stored in r .