C++ 3ms Concise with Explanations


  • 0
    B

    Not the fastest or most memory efficient, but I it's pretty fast and I hope it's clear. I'm using pre and suc to store the links, kinda like a graph I guess. But it's different from a normal graph in that you not only store the next node, but also its count, because a sum formula may include the same node multiple times. I'm also storing the entire sheet just in an unordered_map sheet, so I don't need to bother with converting keys or initialization, just to make the code a littler more clear.

    class Excel {
    private:
        unordered_map<string,unordered_map<string,int>> pre,suc;
        unordered_map<string,int> sheet;
        
        // loop through a range like "A1:B2"
        // returns {"A1","B1","A2","B2"}
        vector<string> getcells(string range) {
            if (!range.find('.')) return {range};
            
            vector<string> res;
            int colon=range.find(':');
            for (int r=stoi(range.substr(1,colon-1));
                r<=stoi(range.substr(colon+2)); r++) {
                for (int c=range[0]-'A'; c<=range[colon+1]-'A'; c++) {
                    
                    res.push_back(char(c+'A')+to_string(r));
                }
            }
            
            return res;
        }
        
        void update(string cell, int val) {
            int delta=val-sheet[cell];
            queue<string> q;
            q.push(cell);
            
            // when we update a cell, we also need to update
            // all cells that are summing up the current cell
            while (!q.empty()) {
                sheet[q.front()]+=delta;
                for (auto next:suc[q.front()]) {
                    for (int i=0; i<next.second; i++) q.push(next.first);
                }
                q.pop();
            }
        }
        
        void clearlinks(string cell) {
            queue<string> q;
            q.push(cell);
            for (auto p:pre[q.front()]) {
                suc[p.first].erase(cell);
            }
            pre[cell].clear();
        }
    public:
        Excel(int H, char W) {
            
        }
        
        void set(int r, char c, int v) {
            string cell=c+to_string(r);
            
            // this cell will no longer contain any formulas
            // clear links for any previous sum formulas for this cell
            // note: we don't clear links for other cells' sum formulas
            // adding up this cell's value
            clearlinks(cell);
            
            // update value for current cell
            update(cell,v);
        }
        
        int get(int r, char c) {
            return sheet[c+to_string(r)];
        }
        
        int sum(int r, char c, vector<string> strs) {
            string cell=c+to_string(r);
            
            // clear links for any previous sum formulas for this cell
            // note: we don't clear links for other cells' sum formulas
            // adding up this cell's value
            clearlinks(cell);
            
            // set links for the new sum formulas
            for (string v:strs) {
                for (string cur:getcells(v)) {
                    pre[cell][cur]++;
                    suc[cur][cell]++;
                }
            }
            
            // update value for current cell
            int val=0;
            for (auto m:pre[cell]) {
                val+=sheet[m.first]*m.second;
            }
            update(cell,val);
            
            return val;
        }
    };
    

Log in to reply
 

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