What is the primary pattern used in "Check if There Is a Valid Parentheses String Path"?

The problem uses state transition dynamic programming to track parentheses balance while traversing the grid.

How do I efficiently traverse the grid for valid parentheses paths?

You can traverse the grid by checking the balance of parentheses at each step, using dynamic programming and memoization to store intermediate results.

What happens if I do not use memoization in this problem?

Without memoization, your solution may repeatedly calculate the same results, leading to higher time complexity and slower performance.

What are some common mistakes when solving this problem?

Common mistakes include not tracking the parentheses balance correctly, failing to consider all valid directions for movement, and not using memoization effectively.

How does this problem relate to other dynamic programming grid problems?

This problem shares similarities with other grid-based dynamic programming problems, such as those that involve pathfinding or maintaining a state during traversal, where balancing state transitions is crucial.

#2267

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

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

一个括号字符串是一个非空且只包含 '(' 和 ')' 的字符串。如果下面任意条件为真，那么这个括号字符串就是合法的。字符串是 () 。字符串可以表示为 AB （ A 连接 B ）， A 和 B 都是合法括号序列。字符串可以表示为 (A) ，其中 A 是合法括号序列。给你一个 …

数组动态规划矩阵

题目描述

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

字符串是 () 。
字符串可以表示为 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] 要么是 '(' ，要么是 ')' 。

lightbulb

解题思路

方法一：DFS + 剪枝

我们记矩阵的行数为 $m$ ，列数为 $n$ 。

如果 $m + n - 1$ 为奇数，或者左上角和右下角的括号不匹配，那么一定不存在合法路径，直接返回 $\text{false}$ 。

否则，我们设计一个函数 $\textit{dfs}(i, j, k)$ ，表示从 $(i, j)$ 出发，且当前括号的平衡度为 $k$ ，是否存在合法路径。其中，平衡度 $k$ 的定义为：从 $(0, 0)$ 到 $(i, j)$ 的路径中，左括号的个数减去右括号的个数。

如果平衡度 $k$ 小于 $0$ 或者大于 $m + n - i - j$ ，那么一定不存在合法路径，直接返回 $\text{false}$ 。如果 $(i, j)$ 正好是右下角的格子，那么只有当 $k = 0$ 时才存在合法路径。否则，我们枚举 $(i, j)$ 的下一个格子 $(x, y)$ ，如果 $(x, y)$ 是合法的格子且 $\textit{dfs}(x, y, k)$ 为 $\text{true}$ ，那么就存在合法路径。

时间复杂度 $O(m \times n \times (m + n))$ ，空间复杂度 $O(m \times n \times (m + n))$ 。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def hasValidPath(self, grid: List[List[str]]) -> bool:
        @cache
        def dfs(i: int, j: int, k: int) -> bool:
            d = 1 if grid[i][j] == "(" else -1
            k += d
            if k < 0 or k > m - i + n - j:
                return False
            if i == m - 1 and j == n - 1:
                return k == 0
            for a, b in pairwise((0, 1, 0)):
                x, y = i + a, j + b
                if 0 <= x < m and 0 <= y < n and dfs(x, y, k):
                    return True
            return False

        m, n = len(grid), len(grid[0])
        if (m + n - 1) % 2 or grid[0][0] == ")" or grid[m - 1][n - 1] == "(":
            return False
        return dfs(0, 0, 0)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate identify the need for dynamic programming to handle the state transitions effectively?
question_mark
Do they recognize the importance of validating prefixes to maintain the balance of parentheses?
question_mark
Can they explain the significance of memoization in reducing redundant calculations for optimal performance?

warning

常见陷阱

外企场景

error
Failing to track parentheses balance properly, leading to invalid paths.
error
Not considering all possible directions (up, down, left, right) during grid traversal.
error
Overlooking the importance of memoization, which could lead to excessive time complexity.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider implementing this solution for grids containing other types of characters or constraints.
arrow_right_alt
Explore how the solution changes when diagonal movement is allowed in the grid.
arrow_right_alt
Try optimizing the solution with additional techniques like depth-first search (DFS) combined with dynamic programming.

help

常见问题

外企场景

继续练习

#2304 网格中的最小路径代价 #2328 网格图中递增路径的数目 #2435 矩阵中和能被 K 整除的路径