python dfs + memorization


  • 0
    X
    def c2i(c): return ord(c) - ord('A') + 1
    def resetcac(cac):
        xsz, ysz = len(cac), len(cac) and len(cac[0])
        return [[None] * ysz for _ in range(xsz)]
    
    class Excel(object):
    
        def __init__(self, H, W):
            """
            :type H: int
            :type W: str
            """
            W = c2i(W)
            H += 1
            W += 1
            self.valm = [[0] * W for _ in range(H)]
            self.cacm = [[0] * W for _ in range(H)]
    
        def set(self, r, c, v):
            """
            :type r: int
            :type c: str
            :type v: int
            :rtype: void
            """
            self.cacm = resetcac(self.cacm)
            self.valm[r][c2i(c)] = v
            
        def get(self, r, c):
            """
            :type r: int
            :type c: str
            :rtype: int
            """
            c = c2i(c)
            def dfs(r, c):
                v = self.cacm[r][c]
                if v is not None:
                    return v
                v = self.valm[r][c]
                if not isinstance(v, int):
                    v = sum( dfs(r, c) * cnt for (r, c), cnt in v.items() )
                self.cacm[r][c] = v
                return v
            return dfs(r, c)
    
        def sum(self, r, c, strs):
            """
            :type r: int
            :type c: str
            :type strs: List[str]
            :rtype: int
            """
            self.cacm = resetcac(self.cacm)
            self.valm[r][c2i(c)] = parse(strs)
            return self.get(r, c)
    
    def s2xy(s): return int(s[1:]), c2i(s[0])
    
    from collections import Counter
    def parse(strs):
        cells = Counter()
        for s in strs:
            if ':' not in s:
                cells[s2xy(s)] += 1
            else:
                tl, br = s.split(':')
                x0, y0 = s2xy(tl)
                x1, y1 = s2xy(br)
                for x in range(x0, x1+1):
                    for y in range(y0, y1+1):
                        cells[x, y] += 1
        return cells
            
    # Your Excel object will be instantiated and called as such:
    # obj = Excel(H, W)
    # obj.set(r,c,v)
    # param_2 = obj.get(r,c)
    # param_3 = obj.sum(r,c,strs)
    

Log in to reply
 

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