Share an easy-to-understand simple 13ms recursive solution


  • 0

    Well, this code is adapted (originally written in Python) from the Coursera course Principles of Computing offered by Rice University. It may not be the most efficient code, but I found it to be easy to understand, especially in the part of generating all the gray codes (function grayCodeHelper()).

    class Solution {
    public:
        vector<string> grayCodeHelper(int n) {
            vector<string> ret;
            ret.push_back("");
            if (n == 0) return ret;
            vector<string> all_but_first = grayCodeHelper(n - 1);
            vector<string> ans;
            for (auto code : all_but_first)
                ans.push_back("0" + code);
            reverse(all_but_first.begin(), all_but_first.end());
            for (auto code : all_but_first)
                ans.push_back("1" + code);
            return ans;
        }
        int bin_to_dec(string code) {
            if (code.length() == 0) return 0;
            return 2 * bin_to_dec(code.substr(0, code.length() - 1)) + code[code.length() - 1] - '0';
        }
        vector<int> grayCode(int n) {
            vector<int> ans;
            vector<string> codes = grayCodeHelper(n);
            for (auto code : codes)
                ans.push_back(bin_to_dec(code));
            return ans;
        }
    };
    

Log in to reply
 

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