c++ non-recursive rate based formula


  • 0
    J

    I haven't seen anyone do it this way so I thought I would give it a shot. I don't really know what to call it other using a formulaic strategy. See below for explanation.

    #include<iostream>
    #include<cmath>
    #include<vector>
    #include<string>
    #include<unordered_map>
    #include<unordered_set>
    
    using namespace std;
    
    class Solution {
            public:
                    vector<string> letterCombinations(string digits) {
                            if(digits.size() == 0 || containsUnmappable(digits)) {
                                    vector<string> empty;
                                    return empty;
                            }
    
                            int vecSz = getVecSize(digits); //figure out the size of the return vector and alloc to that size
                            vector<string> retVec(vecSz);
    
                            for(int i = 1; i <= vecSz; i++){
                                    retVec[i - 1] = buildString(i, digits);
                            }
                            return retVec;
                    }
            private:
                    string buildString(int i, const string& digits){
                            int r(1), c, l(digits.size()), v(1); //rate, char in string position, length of digits string, current/last digits char length;
                            string retString(l, ' ');
                            for(int p = l - 1; p >= 0; p--){
                                    r = r*v;
                                    v = charMap[digits[p]].size();
                                    c = (i/r)%v;
                                    retString[p] = charMap[digits[p]][c];
                            }
                            return retString;
                    }
    
                    int getVecSize(const string& digits){
                            int r(1);
                            for(int i = digits.size() - 1; i >= 0; i--){
                                    r *= charMap[digits[i]].length();
                            }
                            return r;
                    }
    
                    bool containsUnmappable(const string& digits){
                            unordered_set<char> mappable = {'2','3','4','5','6','7','8','9'};
                            for(int i(0), sz(digits.size()); i < sz; i++)
                            {
                                    if(mappable.find(digits[i]) == mappable.end())
                                            return true;
                            }
                            return false;
                    }
    
                    unordered_map<char, string> charMap = {
                            {'2',"abc"},
                            {'3',"def"},
                            {'4',"ghi"},
                            {'5',"jkl"},
                            {'6',"mno"},
                            {'7',"pqrs"},
                            {'8',"tuv"},
                            {'9',"wxyz"}
                    };
    
    
    };
    

    You can figure out any combination with just the iteration number and digits string through a rate formula.

    Each place in the digits string has a rate of character repetition. If you manually write out each iteration you can see the repetition.

    For example:
    432
    gda
    gdb
    gdc
    gea
    geb
    gec
    gfa
    gfb
    gfc
    hda

    The last digit '2' has a character repetition of once every iteration, so every iteration it goes to it's digits next character. '3' has a character repetition of 3, so after 3 iterations it goes to it's next digit. '4' has a character repetition of 9 and so on.

    The formula for this repetition is Current_rate * Previous_Digits_Characters_Length starting at the last digit and working backwards. So starting at 2, the rate is 1 * 1(There is no last previous digit for 2 since it is the first one so it's rate will always be 1). The rate for 3 is 1 * 3, since the digit '2' has 3 possible characters 'abc'. 4's rate is 3 * 3, since the current rate is 3 and '3' has 3 possible characters 'def'.

    Once we know the rate of each place we can figure out what character the place should have based on what iteration it is by the formula
    character = (iteration/rate) % Current_Digit_Characters_Length


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.