C++, 0ms, No backtracking, or Queue. Similar to counting number.


  • 2

    I have a different approach and it is more intuitive to me. This is similar to printing all numbers with k digits. For example k=3, you start at 000, then you keep coming up: 001, 002, 003, ... until you reach 009, then reset last bit, and increase the next bit to 010, then 011, 012, etc.

    So we can solve this problem in a similar way. If our input string is "23". Because 2 = "abc", 3 = "def", we can start from the smallest "ad", then go up: "ae", "af", then we have to reset last char from "f" to "d" and we have "bd", "be", "bf", etc. This way, we don't need backtracking, recursive, or List.

    Hope this helps for some people.

    vector<string> letterCombinations(string digits) {
        vector<string> R;
        if (digits.empty()) return R;
        string a[8] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        int n = digits.size();
        vector<int> v(n, 0);
        
        // Initialize string V
        string S = "";
        for (int i=0; i<n; i++)
            S += a[digits[i]-'0'-2][0];
        
        while (true) {
            R.push_back(S);
            int j = n-1;
            v[j]++;
            while (j>0 && v[j]==a[digits[j]-'0'-2].size()) {
                v[j] = 0;
                S[j] = a[digits[j]-'0'-2][0];
                v[--j]++;
            }
            
            //Check to see if outta range yet
            if (v[0]==a[digits[0]-'0'-2].size()) break;
            else S[0] = a[digits[0]-'0'-2][v[0]];
            
            S[j] = a[digits[j]-'0'-2][v[j]];
        }
        return R;
    }

  • 0
    U

    great work and good observation! i've been thinking about turning my previous recursive solution to simple loop one with some complex bookkeeping and various stacks, now i decided to forget it.


Log in to reply
 

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