Problem statement

https://binarysearch.com/problems/Excel-Spreadsheet/

Solution

The idea is to use recursion here: when we have value, just return it, when we have formula, compute it recursively.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def solve(self, M):
        is_num = lambda x: x.isdigit() or x[0] == "-"
        get = lambda x: int(x) if is_num(x) else dp(int(x[1:])-1, ord(x[0]) - 65)

        m, n = len(M), len(M[0])
        @lru_cache(None)
        def dp(i, j):
            if is_num(M[i][j]): return int(M[i][j])
            if M[i][j][0] == "=":
                sgn = 1 if "+" in M[i][j] else -1
                sg = "+" if sgn == 1 else "-"
                x, y = M[i][j][1:].split(sg)
                return get(x) + get(y) * sgn
            return get(M[i][j])

        for i in range(m):
            for j in range(n):
                M[i][j] = str(dp(i, j))

        return M