631. Design Excel Sum Formula

• Time: Constructor: $O(\texttt{height} \cdot \texttt{width})$, set(row: int, column: chr, val: int), get(row: int, column: chr): $O(1)$, sum(row: int, column: chr, numbers: List[str]): $O(|\texttt{numbers}|)$
• Space: $O(\texttt{height} \cdot \texttt{width})$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 struct Cell { int val = 0; unordered_map posCount; // {pos: count} }; class Excel { public: Excel(int height, char width) : width(width), sheet(height, vector(width)) {} void set(int row, char column, int val) { getCell(row, column) = {val, {}}; } int get(int row, char column) { const Cell& cell = getCell(row, column); if (cell.posCount.empty()) return cell.val; int val = 0; for (const auto& [pos, count] : cell.posCount) val += get(pos / width + 1, pos % width + 'A') * count; return val; } int sum(int row, char column, vector numbers) { getCell(row, column).posCount = parse(numbers); return get(row, column); } private: int width; vector> sheet; Cell& getCell(int row, char column) { return sheet[row - 1][column - 'A']; } unordered_map parse(const vector& numbers) { unordered_map count; for (const string& s : numbers) { const auto [startRow, startCol, endRow, endCol] = parse(s); for (int i = startRow - 1; i < endRow; ++i) for (int j = startCol - 'A'; j < endCol - 'A' + 1; ++j) ++count[i * width + j]; } return count; } tuple parse(const string& s) { if (s.find(':') == string::npos) return {stoi(s.substr(1)), s[0], stoi(s.substr(1)), s[0]}; const int colonIndex = s.find_first_of(':'); const string& l = s.substr(0, colonIndex); const string& r = s.substr(colonIndex + 1); return {stoi(l.substr(1)), l[0], stoi(r.substr(1)), r[0]}; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 class Cell { public int val = 0; public Map posCount = new HashMap<>(); // {pos, count} public Cell(int val, Map posCount) { this.val = val; this.posCount = posCount; } } class Excel { public Excel(int height, char width) { this.width = width; this.sheet = new Cell[height][width]; for (int i = 0; i < height; ++i) for (int j = 0; j < width; ++j) sheet[i][j] = new Cell(0, null); } public void set(int row, char column, int val) { sheet[row - 1][column - 'A'] = new Cell(val, null); } public int get(int row, char column) { Cell cell = sheet[row - 1][column - 'A']; if (cell.posCount == null) return cell.val; int val = 0; for (Map.Entry entry : cell.posCount.entrySet()) { final int pos = entry.getKey(); final int count = entry.getValue(); val += get(pos / width + 1, (char) ((pos % width) + 'A')) * count; } return val; } public int sum(int row, char column, String[] numbers) { sheet[row - 1][column - 'A'].posCount = parse(numbers); return get(row, column); } private int width; private Cell[][] sheet; private Map parse(String[] numbers) { Map count = new HashMap<>(); for (final String s : numbers) { Pair tokens = parse(s); final int startRow = Integer.parseInt(tokens.getKey().substring(1)); final char startCol = tokens.getKey().charAt(0); final int endRow = Integer.parseInt(tokens.getValue().substring(1)); final char endCol = tokens.getValue().charAt(0); for (int i = startRow - 1; i < endRow; ++i) for (int j = startCol - 'A'; j < endCol - 'A' + 1; ++j) count.merge(i * width + j, 1, Integer::sum); } return count; } private Pair parse(final String s) { if (!s.contains(":")) return new Pair<>(s, s); String[] tokens = s.split(":"); return new Pair<>(tokens[0], tokens[1]); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Cell: def __init__(self, val: int, posCount: Optional[Dict[Tuple[int, int], int]]): self.val = val self.posCount = posCount # {pos, count} class Excel: def __init__(self, height: int, width: str): self.sheet = [[Cell(0, None) for i in range(height)] for _ in range(ord(width) - ord('A') + 1)] def set(self, row: int, column: str, val: int) -> None: self.sheet[row - 1][ord(column) - ord('A')] = Cell(val, None) def get(self, row: int, column: str) -> int: cell = self.sheet[row - 1][ord(column) - ord('A')] if cell.posCount: return sum(self.get(*pos) * freq for pos, freq in cell.posCount.items()) return cell.val def sum(self, row: int, column: str, numbers: List[str]) -> int: self.sheet[row - 1][ord(column) - ord('A')].posCount = self._parse(numbers) return self.get(row, column) def _parse(self, numbers: List[str]): count = collections.Counter() for n in numbers: s, e = n.split(':')[0], n.split(':')[1] if ':' in n else n for i in range(int(s[1:]), int(e[1:]) + 1): for j in range(ord(s[0]) - ord('A'), ord(e[0]) - ord('A') + 1): count[(i, chr(j + ord('A')))] += 1 return count