solution/2200-2299/2267.Check if There Is a Valid Parentheses String Path/Solution.py at main

main

leetcode-ion

388 issues
2 pull requests
5,000 files
1 active branch

List view

solution\2200-2299\2267.Check if There Is a Valid Parentheses String Path\Solution.py

1 Complexity
1 Complexity / M
0 Duplication
1 Churn
19 Lines
18 Lines of Code
1 Methods
18 LOC / Method

class Solution:
    def hasValidPath(self, grid: List[List[str]]) -> bool:
        @cache
        def dfs(i, j, t):
            if grid[i][j] == '(':
                t += 1
            else:
                t -= 1
            if t < 0:
                return False
            if i == m - 1 and j == n - 1:
                return t == 0
            for x, y in [(i + 1, j), (i, j + 1)]:
                if x < m and y < n and dfs(x, y, t):
                    return True
            return False

        m, n = len(grid), len(grid[0])
        return dfs(0, 0, 0)