Python 69 ms with detailed comments


  • 0
    S

    Once a formula is set to cell1, then we should build a bidirectional relation between cell1 and the cells in the formula, say cell2. In this case, we call cell1 as one output of cell2 and cell2 as an input of cell1. Note that an input may appear multiple times in a single formula.

    • If a cell's value is changed, its outputs should change correspondingly.
    • If a cell's formula is changed or emptied, then the connections between this cell and its inputs should be cut off.
    class Cell:
        def __init__(self, val=0):
            self.val = val
            self.inputs = collections.defaultdict(int)  # inputs may be duplicate
            self.outputs = set()
    
        def set_value(self, v):
            """
            Set this cell's value to be v
            """
            # update the related outputs
            for output_cell in self.outputs:
                output_cell._update(self, v - self.val)
            self.val = v
    
        def _update(self, input_cell, delta):
            """
            Update this cell's value due to the delta increase of an input cell's value
            """
            v = self.val + self.inputs[input_cell] * delta
            self.set_value(v)
    
        def remove_input_cell(self, cell):
            """
            Remove the association of one input cell
            """
            # note: this association is bi-directional
            del self.inputs[cell]
            cell.outputs.remove(self)
    
        def clear_input_cells(self):
            """
            Clear all the input cells
            """
            for input_cell in self.inputs:
                input_cell.outputs.remove(self)
            self.inputs.clear()
    
        def add_input_cell(self, cell):
            """
            Add an input cell
            """
            self.inputs[cell] += 1
            cell.outputs.add(self)
    
    
    class Excel(object):
        def __init__(self, H, W):
            """
            :type H: int
            :type W: str
            """
            self.C = [[Cell() for _ in range(ord(W) - ord('A') + 1)] for _ in range(H)]
    
        def _get_cell(self, r, c):
            return self.C[r - 1][ord(c) - ord('A')]
    
        def set(self, r, c, v):
            """
            :type r: int
            :type c: str
            :type v: int
            :rtype: void
            """
            cell = self._get_cell(r, c)
            cell.set_value(v)
            # no formula now, clear the previous inputs
            cell.clear_input_cells()
    
        def get(self, r, c):
            """
            :type r: int
            :type c: str
            :rtype: int
            """
            cell = self._get_cell(r, c)
            return cell.val
    
        def sum(self, r, c, strs):
            """
            :type r: int
            :type c: str
            :type strs: List[str]
            :rtype: int
            """
            s = 0
            target_cell = self._get_cell(r, c)
            target_cell.clear_input_cells()  # the formula is reset
            for cell in self._parse_formula(strs):
                target_cell.add_input_cell(cell)
                s += cell.val
            target_cell.set_value(s)
            return s
    
        def _parse_formula(self, strs):
            """
            Yield the cells specified by the formula
            """
            for s in strs:
                ss = s.split(':')
                if len(ss) == 1:  # a single cell
                    c = ss[0][0]
                    r = int(ss[0][1:])
                    yield self._get_cell(r, c)
                else:  # a rectangle area
                    c1, r1 = ss[0][0], int(ss[0][1:])
                    c2, r2 = ss[1][0], int(ss[1][1:])
                    for r in range(r1, r2 + 1):
                        for c in [chr(a) for a in range(ord(c1), ord(c2) + 1)]:
                            yield self._get_cell(r, c)

Log in to reply
 

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