title
一个括号字符串是一个 非空 且只包含 '(' 和 ')' 的字符串。如果下面 任意 条件为 真 ，那么这个括号字符串就是 合法的 。
- 字符串是
()。 - 字符串可以表示为
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.lengthn == grid[i].length1 <= m, n <= 100grid[i][j]要么是'('，要么是')'。
solution
return true when we find the valid path consisting of valid parentheses. which means at the end, it needs to be guarantted that the number of open brackets is equal with the number of close brackets.
Plus, at the every position of this valid path, the number of open brackets needs to be equal or greater than the number of close brackets so that stop useless/unnecessary searching.
class Solution:
def hasValidPath(self, grid: List[List[str]]) -> bool:
m, n = len(grid), len(grid[0])
import functools
@functools.lru_cache(None)
def dfs(x, y, cnt):
if cnt < 0:
return False
if grid[x][y] == "(":
cnt += 1
else:
cnt -= 1
if (x, y) == (m - 1, n - 1) and cnt == 0:
return True
if y + 1 < n and dfs(x, y + 1, cnt):
return True
if x + 1 < m and dfs(x + 1, y, cnt):
return True
return False
return dfs(0, 0, 0)
if __name__ == '__main__':
f = Solution().hasValidPath
print("actual:", f(grid=[["(", "(", "("], [")", "(", ")"], ["(", "(", ")"], ["(", "(", ")"]]), "should:", True)
print("actual:", f(grid=[[")", ")"], ["(", "("]]), "should:", False)