| comments | difficulty | edit_url | rating | source | tags | |||
|---|---|---|---|---|---|---|---|---|
true |
困难 |
2084 |
第 292 场周赛 Q4 |
|
一个括号字符串是一个 非空 且只包含 '(' 和 ')' 的字符串。如果下面 任意 条件为 真 ，那么这个括号字符串就是 合法的 。
- 字符串是
()。 - 字符串可以表示为
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]要么是'('，要么是')'。
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)class Solution {
private boolean[][][] vis;
private char[][] grid;
private int m;
private int n;
public boolean hasValidPath(char[][] grid) {
m = grid.length;
n = grid[0].length;
this.grid = grid;
vis = new boolean[m][n][m + n];
return dfs(0, 0, 0);
}
private boolean dfs(int i, int j, int t) {
if (vis[i][j][t]) {
return false;
}
vis[i][j][t] = true;
t += grid[i][j] == '(' ? 1 : -1;
if (t < 0) {
return false;
}
if (i == m - 1 && j == n - 1) {
return t == 0;
}
int[] dirs = {0, 1, 0};
for (int k = 0; k < 2; ++k) {
int x = i + dirs[k], y = j + dirs[k + 1];
if (x < m && y < n && dfs(x, y, t)) {
return true;
}
}
return false;
}
}bool vis[100][100][200];
int dirs[3] = {1, 0, 1};
class Solution {
public:
bool hasValidPath(vector<vector<char>>& grid) {
memset(vis, 0, sizeof(vis));
return dfs(0, 0, 0, grid);
}
bool dfs(int i, int j, int t, vector<vector<char>>& grid) {
if (vis[i][j][t]) return false;
vis[i][j][t] = true;
t += grid[i][j] == '(' ? 1 : -1;
if (t < 0) return false;
int m = grid.size(), n = grid[0].size();
if (i == m - 1 && j == n - 1) return t == 0;
for (int k = 0; k < 2; ++k) {
int x = i + dirs[k], y = j + dirs[k + 1];
if (x < m && y < n && dfs(x, y, t, grid)) return true;
}
return false;
}
};func hasValidPath(grid [][]byte) bool {
m, n := len(grid), len(grid[0])
vis := make([][][]bool, m)
for i := range vis {
vis[i] = make([][]bool, n)
for j := range vis[i] {
vis[i][j] = make([]bool, m+n)
}
}
var dfs func(int, int, int) bool
dfs = func(i, j, t int) bool {
if vis[i][j][t] {
return false
}
vis[i][j][t] = true
if grid[i][j] == '(' {
t += 1
} else {
t -= 1
}
if t < 0 {
return false
}
if i == m-1 && j == n-1 {
return t == 0
}
dirs := []int{1, 0, 1}
for k := 0; k < 2; k++ {
x, y := i+dirs[k], j+dirs[k+1]
if x < m && y < n && dfs(x, y, t) {
return true
}
}
return false
}
return dfs(0, 0, 0)
}