6059. 检查是否有合法括号字符串路径

Difficulty
Hard
Tags
DFS
URL
https://leetcode-cn.com/problems/check-if-there-is-a-valid-parentheses-string-path/
Star
一个括号字符串是一个 非空 且只包含 '(' 和 ')' 的字符串。如果下面 任意 条件为 真 ，那么这个括号字符串就是 合法的 。
  • 字符串是 () 。
  • 字符串可以表示为 AB（A 连接 B），A 和 B 都是合法括号序列。
  • 字符串可以表示为 (A) ，其中 A 是合法括号序列。
给你一个 m x n 的括号网格图矩阵 grid 。网格图中一个 合法括号路径 是满足以下所有条件的一条路径：
  • 路径开始于左上角格子 (0, 0) 。
  • 路径结束于右下角格子 (m - 1, n - 1) 。
  • 路径每次只会向 下 或者向 右 移动。
  • 路径经过的格子组成的括号字符串是 合法 的。
如果网格图中存在一条 合法括号路径 ，请返回 true ，否则返回 false 。
示例 1：
notion imagenotion image
输入：grid = [["(","(","("],[")","(",")"],["(","(",")"],["(","(",")"]]
输出：true
解释：上图展示了两条路径，它们都是合法括号字符串路径。
第一条路径得到的合法字符串是 "()(())" 。
第二条路径得到的合法字符串是 "((()))" 。
注意可能有其他的合法括号字符串路径。
示例 2：
输入：grid = [[")",")"],["(","("]]
输出：false
解释：两条可行路径分别得到 "))(" 和 ")((" 。由于它们都不是合法括号字符串，我们返回 false 。
提示：
  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 100
  • grid[i][j] 要么是 '(' ，要么是 ')' 。

DFS 加状态

思路
判断括号是否合法的方式，记录左右括号的数目，只要保证过程中左括号数永远大于等于右括号数目，且最后左右括号数目相同，那么就合法。然后可以用左括号数减右括号数 作为状态。
容易想到的方法就是DFS， 但是常规dfs会超时。所以需要记录每个时刻的状态。
题解
class Solution:
    def hasValidPath(self, grid: List[List[str]]) -> bool:
        if grid[0][0] == ")" or grid[-1][-1] == "(":
            return False
        
        if (len(grid) + len(grid[-1]) - 1) % 2 == 1:
            return False

        self.visited = [[[False] * (len(grid) * len(grid[0])) for _ in range(len(grid[0]))] for _ in range(len(grid))]

        self.visited[0][0][0] = True
        return self.dfs(l=0, r=0, grid=grid, row=0, col=0)

    def dfs(self, l, r, grid, row, col):
        if row < 0 or row >= len(grid) or col < 0 or col >= len(grid[0]):
            return False

        if l < r or l > (len(grid) + len(grid[0]) -1) // 2:
            return False

        if grid[row][col] == "(":
            l += 1
        else:
            r += 1     

        if row == len(grid)-1 and col == len(grid[0])-1:
            if l == r:
                return True
            return False

        if self.visited[row][col][l-r]:
            return False

        self.visited[row][col][l-r] = True

        return self.dfs(l, r, grid, row+1, col) or\
            self.dfs(l, r, grid, row, col+1)