631. Design Excel Sum Formula

Design the basic function of Excel and implement the function of the sum formula.

Implement the Excel class:

• Excel(int height, char width) Initializes the object with the height and the width of the sheet. The sheet is an integer matrix mat of size height x width with the row index in the range [1, height] and the column index in the range [‘A’, width]. All the values should be zero initially.
• void set(int row, char column, int val) Changes the value at mat[row][column] to be val.
• int get(int row, char column) Returns the value at mat[row][column].
• int sum(int row, char column, List numbers) Sets the value at mat[row][column] to be the sum of cells represented by numbers and returns the value at mat[row][column]. This sum formula should exist until this cell is overlapped by another value or another sum formula. numbers[i] could be on the format:

• “ColRow” that represents a single cell.

• For example, “F7” represents the cell mat[7][‘F’].

• “ColRow1:ColRow2” that represents a range of cells. The range will always be a rectangle where “ColRow1” represent the position of the top-left cell, and “ColRow2” represents the position of the bottom-right cell.

• For example, “B3:F7” represents the cells mat[i][j] for 3 <= i <= 7 and ‘B’ <= j <= ‘F’.

Note: You could assume that there will not be any circular sum reference.

• For example, mat[1][‘A’] == sum(1, “B”) and mat[1][‘B’] == sum(1, “A”).

struct Cell {
    int val;
    vector<Cell*> child;
    Cell(int val) :val(val) {}
    Cell(vector<Cell*> c):val(0), child(c){}
    void change(vector<Cell*> c) {
        child = c;
    }
    void change(int v) {
        val = v;
        child.clear();
    }
    int get() {
        if(child.empty())
            return val;
        int res = 0;
        for(auto& c : child) {
            res += c->get();
        }
        return res;
    }
};
class Excel {
    vector<vector<Cell*>> matrix;
    pair<int,int> parseSingle(string s) {
        int w = s[0] - 'A';
        int h = stoi(s.substr(1));
        return {h, w};
    }
public:
    Excel(int height, char width) {
        matrix = vector<vector<Cell*>>(27,vector<Cell*>(27, NULL));
        for(int i = 0; i < 27; i++)
            for(int j = 0; j < 27; j++)
                matrix[i][j] = new Cell(0);
    }

    void set(int row, char column, int val) {
        int h = row, w = column - 'A';
        matrix[h][w]->change(val);
    }

    int get(int row, char column) {
        int h = row, w = column - 'A';
        return matrix[h][w]->get();
    }

    int sum(int row, char column, vector<string> numbers) {
        int h = row, w = column - 'A';
        vector<Cell*> cells;
        for(auto& n : numbers) {
            if(n.find(':') == string::npos) {
                auto [r, c] = parseSingle(n);
                cells.push_back(matrix[r][c]);
            } else {
                auto [r1, c1] = parseSingle(n.substr(0, n.find(':')));
                auto [r2, c2] = parseSingle(n.substr(n.find(':') + 1));
                for(int i = r1; i <= r2; i++) {
                    for(int j = c1; j <= c2; j++) {
                        cells.push_back(matrix[i][j]);
                    }
                }
            }
        }

        matrix[h][w]->change(cells);
        
        return matrix[h][w]->get();
    }
};

/**
 * Your Excel object will be instantiated and called as such:
 * Excel* obj = new Excel(height, width);
 * obj->set(row,column,val);
 * int param_2 = obj->get(row,column);
 * int param_3 = obj->sum(row,column,numbers);
 */