Interesting iterative solution (C++, 0ms)


  • 3
    L

    Of couse recursive solution is easy understand and clear, but this iterative solution is interesting too:

    const string table[8] = { "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
    
    vector<string> letterCombinations(string digits) {
        int n = digits.size();
        if(n==0) return vector<string>(0,"");
        int total=1;
        for(char d : digits) 
            total*= table[d-'2'].size();
        string s(n,'\0');
        vector<string> results(total,s);
        int repeat=1;
        for(int i=0;i<n;i++){
            int j=0;
            string t = table[digits[i]-'2'];
            while(j<total){
                for(char c : t) {
                    for(int k=0;k<repeat;k++){
                        results[j++][i]=c;
                    }
                }
            }
            repeat*=t.size();
        }
        return results;
    }
    // 1. pqrspqrspqrspqrs...
    // 2. ddddeeeeffffdddd...
    // 3. aaaaaaaaaaaabbbb...
    

    I think this solution is fit C more. (not C++ or C#)

    1. Sum results (total) and alloc results memory. (n*total)
    2. For each digits.
    3. For each char in table of digit.
    4. Repeat to fill char in the column of results.

    ex.

    1. digits="732"
    2. (4x3x3) x 3chars results
    3. Repeat "pqrs" to fill 1st char for all of results
    4. Repeat "def", per char 4 times to fill 2nd char for all of results
    5. Repeat "abc", per char 43 times* to fill 3nd char for all of results

Log in to reply
 

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