Check if There Is a Valid Parentheses String Path LeetCode solution in Python

1
class Solution:
2
    def hasValidPath(self, grid: List[List[str]]) -> bool:
3
        m = len(grid)
4
        n = len(grid[0])
5

6
        @lru_cache(maxsize=None)
7
        def hasValidPathInner(x, y, cnt):
8
            # cnt variable would act as a counter to track
9
            # the balance of parantheses sequence
10
            if x == m or y == n or cnt < 0:
11
                return False
12

13
            # logic to check the balance of sequence
14
            cnt += 1 if grid[x][y] == "(" else -1
15

16
            # if balanced and end of grid, return True
17
            if x == m - 1 and y == n - 1 and not cnt:
18
                return True
19

20
            return hasValidPathInner(x + 1, y, cnt) or hasValidPathInner(x, y + 1, cnt)
21

22
        return hasValidPathInner(0, 0, 0)