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

标签: 数组 动态规划 矩阵

难度: Hard

一个括号字符串是一个 非空 且只包含 '(' 和 ')' 的字符串。如果下面 任意 条件为 真 ，那么这个括号字符串就是 合法的 。

  • 字符串是 () 。
  • 字符串可以表示为 AB（A 连接 B），A 和 B 都是合法括号序列。
  • 字符串可以表示为 (A) ，其中 A 是合法括号序列。

给你一个 m x n 的括号网格图矩阵 grid 。网格图中一个 合法括号路径 是满足以下所有条件的一条路径：

  • 路径开始于左上角格子 (0, 0) 。
  • 路径结束于右下角格子 (m - 1, n - 1) 。
  • 路径每次只会向 下 或者向 右 移动。
  • 路径经过的格子组成的括号字符串是 合法 的。

如果网格图中存在一条 合法括号路径 ，请返回 true ，否则返回 false 。

示例 1：

输入：grid = [["(","(","("],[")","(",")"],["(","(",")"],["(","(",")"]]
输出：true
解释：上图展示了两条路径，它们都是合法括号字符串路径。
第一条路径得到的合法字符串是 "()(())" 。
第二条路径得到的合法字符串是 "((()))" 。
注意可能有其他的合法括号字符串路径。

示例 2：

输入：grid = [[")",")"],["(","("]]
输出：false
解释：两条可行路径分别得到 "))(" 和 ")((" 。由于它们都不是合法括号字符串，我们返回 false 。

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 100
  • grid[i][j] 要么是 '(' ，要么是 ')' 。

Submission

运行时间: 43 ms

内存: 22.4 MB

class Solution:
    def hasValidPath(self, grid: List[List[str]]) -> bool:
        # 将(记作1  )记作-1 整个路径过程中 和>=0 且到达右下角为0
        n, m = len(grid), len(grid[0])
        if grid[0][0] == ")" or grid[-1][-1] == "(" or (n + m - 1) % 2:
            return False

        @cache
        def dfs(i, j, s):  # 从[i,j]出发是否存在合法路径 s表示前面累计和
            if s > n - i + m - j - 1:
                return False  # 剪枝：即使后面都是 ')' 也不能将 c 减为 0
            if i == n - 1 and j == m - 1:  # 终点一定是 ')'
                return s == 1
            s += 1 if grid[i][j] == "(" else -1
            if s < 0:
                return False
            for ni, nj in (i + 1, j), (i, j + 1):
                if n > ni >= 0 <= nj < m:
                    if dfs(ni, nj, s):
                        return True
            return False

        return dfs(0, 0, 0)

Explain

该题解采用深度优先搜索(DFS)的方式来判断从左上角到右下角是否存在一条合法的括号路径。首先进行了一些初步的判断，例如起点和终点的字符是否符合要求，以及路径长度是否为偶数。DFS函数使用了记忆化来优化搜索过程。在搜索过程中，使用参数s来记录当前路径上'('和')'的数量差，即每遇到'('则s增加1，遇到')'则s减少1。如果在任意点s小于0，说明不可能形成合法的括号序列。另外，如果到达终点时s不等于1，则也不是合法路径。此外，还应用了剪枝技术，如果当前的s已经大于从当前位置到终点所需的最少')'的数量，则可以提前终止搜索。

时间复杂度: O(n*m*2n)

空间复杂度: O(n*m*2n)

class Solution:
    def hasValidPath(self, grid: List[List[str]]) -> bool:
        # Define grid dimensions
        n, m = len(grid), len(grid[0])
        # Early return if the start or end are invalid, or if the path length is odd
        if grid[0][0] == ")" or grid[-1][-1] == "(" or (n + m - 1) % 2:
            return False

        @cache
        def dfs(i, j, s):  # DFS to find a valid path with balance s
            # Prune if the remaining maximum possible ')' cannot balance '('
            if s > n - i + m - j - 1:
                return False
            if i == n - 1 and j == m - 1:  # Check if we reach the end with the exact balance needed
                return s == 1
            s += 1 if grid[i][j] == "(" else -1
            if s < 0:  # Invalid if more ')' than '('
                return False
            # Explore the next possible cells
            for ni, nj in (i + 1, j), (i, j + 1):
                if n > ni >= 0 <= nj < m:
                    if dfs(ni, nj, s):
                        return True
            return False

        return dfs(0, 0, 0)

Explore

在深度优先搜索中使用记忆化是为了避免重复计算相同状态的结果，从而提高算法效率。具体的记忆化策略是使用一个缓存来存储每个状态（当前位置和当前括号差）的搜索结果。在这个题解中，使用`@cache`装饰器实现了记忆化。这意味着每次调用`dfs`函数时，首先检查是否计算过当前状态的结果，如果计算过，则直接返回之前的结果，否则继续执行搜索。这样可以显著减少不必要的计算，尤其是在面对大规模数据和复杂路径时。

在这个题解中，开始状态的`s`值设为0，这代表在起点时括号'('和')'的数量是平衡的，即没有多余的'('或')'。这是因为`s`代表从起点到当前点的路径上，'('和')'的数量差（即'('的数量减去')'的数量）。开始时，由于还未遍历任何格子，因此这个差值为0。

在题解中，要求`s == 1`来判断路径是否合法是因为在到达终点时，理想的情况是路径上的'('比')'多一个，这是因为起点已经被设置为'('且终点被设置为')'，整个路径应该是闭合的。如果`s == 0`，则意味着'('和')'数量完全相等，考虑到起点和终点的括号设置，这将导致路径在没有闭合的情况下结束，因此不是合法的括号字符串路径。

这个剪枝条件基于从当前位置到终点的最大可行步数。`n - i + m - j - 1`计算的是从当前位置(i, j)到终点所需的最小步数。如果`s`（当前'('和')'的数量差）大于这个值，意味着即使之后的每一步都是')'，也无法达到平衡（即无法使得最终'('和')'的数量相等）。因此，如果`s`超过了这个界限，可以判断当前路径无法形成合法的括号序列，从而提前终止搜索。这是一个有效的剪枝策略，能够减少无效搜索，提高效率。