Leetcode每日一题 —— 2267. 检查是否有合法括号字符串路径

魔法师2026-09-29

13093

力扣 LeetCode

2267. 检查是否有合法括号字符串路径 - 力扣（LeetCode）

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

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

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

* 路径开始于左上角格子 (0,...

思路

看完题朴素想法就是递推，‘(’+1，‘)’-1，然后用Hash存储格子可能性。由左边格子和上边格子的可能性推出当前格子的可能性。（注意要排除负数的可能性）

代码```
class Solution {
public boolean hasValidPath(char[][] grid) {
int m = grid.length;
int n = grid[0].length;
HashSet<Integer>[] dp = new HashSet[n];
for (int i = 0; i < n; i++) {
dp[i] = new HashSet<>();
}
dp[0].add(0);
for (int i = 0; i < m; i++) {
HashSet<Integer>[] next = new HashSet[n];
next[0] = new HashSet<>();
int tmp = grid[i][0] == '(' ? 1 : -1;
for (int v : dp[0]) {
if (v + tmp >= 0) {
next[0].add(v + tmp);
}
}
for (int j = 1; j < n; j++) {
tmp = grid[i][j] == '(' ? 1 : -1;
next[j] = new HashSet<>();
for (int v : dp[j]) {
if (v + tmp >= 0) {
next[j].add(v + tmp);
}
}
for (int v : next[j - 1]) {
if (v + tmp >= 0) {
next[j].add(v + tmp);
}
}
}
dp = next;
}
return dp[n - 1].contains(0);
}
}


HashSet有些慢了，换成`int[10000]`来优化速度，用max记录最大值。比较丑陋，不过暂时没时间继续了。

代码```
class Solution {
    public boolean hasValidPath(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int top = m * n / 2;
        int[][] dp = new int[n][10000];
        int max = 0;
        dp[0][0] = 1;
        for (char[] chars : grid) {
            if (chars[0] == '(') {
                for (int x = max; x >= 0; x--) {
                    if (dp[0][x] == 1) {
                        dp[0][x + 1] = 1;
                        dp[0][x] = 0;
                    } else {
                        dp[0][x + 1] = 0;
                    }
                }
                if (dp[0][max + 1] == 1) {
                    max++;
                }
            } else {
                dp[0][0] = 0;
                for (int x = 1; x <= max; x++) {
                    if (dp[0][x] == 1) {
                        dp[0][x - 1] = 1;
                    } else {
                        dp[0][x - 1] = 0;
                    }
                    dp[0][x] = 0;
                }
            }
            for (int j = 1; j < n; j++) {
                if (chars[j] == '(') {
                    for (int x = max; x >= 0; x--) {
                        if (dp[j][x] == 1) {
                            dp[j][x + 1] = 1;
                            dp[j][x] = 0;
                        } else {
                            dp[j][x + 1] = 0;
                        }
                    }
                    for (int x = 0; x <= max; x++) {
                        if (dp[j - 1][x] == 1) {
                            dp[j][x + 1] = 1;
                        }
                    }
                } else {
                    for (int x = 1; x <= max; x++) {
                        if (dp[j][x] == 1) {
                            dp[j][x - 1] = 1;
                            dp[j][x] = 0;
                        } else {
                            dp[j][x - 1] = 0;
                        }
                    }
                    for (int x = 1; x <= max; x++) {
                        if (dp[j - 1][x] == 1) {
                            dp[j][x - 1] = 1;
                        }
                    }
                }
                if (dp[j][max + 1] == 1) {
                    max++;
                }
            }
        }
        return dp[n - 1][0] == 1;
    }
}

主楼

SomeBottle2026-09-29
11179
用记忆化 DFS 写的话，思路很清晰。```
class Solution {
public:
bool hasValidPath(vector<vector<char>>& grid) {
// 只要存在一条合法的就行
// 因为从左上角开始，右下角结束，路径长度总是相同的
// 过程中左括号数量肯定 >= 右括号数量
// 直接 DFS
bool res=false;
int m=grid.size(),n=grid[0].size();
if(((m+n-1)&1)==1){
// 路径长度为奇数，不可能
return false;
}
bool visited[m][n][m+n-1];
memset(visited,0,sizeof(visited));
auto dfs=[&](this auto&& self,int row,int col,int left) -> void {
if(res)
return;
if(visited[row][col][left]) // 不重复访问相同状态
return;
visited[row][col][left]=true;
if(grid[row][col]=='('){
left++;
}else if(grid[row][col]==')'){
left--;
}
// cout<<"ROW: "<<row<<" COL: "<<col<<" LEFT: "<<left<<endl;
if(left<0){
// 左括号数量 < 右括号数量
return;
}
if(left==0&&row==m-1&&col==n-1){
res=true;
return;
}
// 要不往右要不往下走
if(col<n-1){
self(row,col+1,left);
}
if(row<m-1){
self(row+1,col,left);
}
};
dfs(0,0,0);
return res;
}
};
#1
Lvvvv2026-09-29
17266
按理来说这个级别的题目不该hard。不过依然慢..```
class Solution {
public:
bool hasValidPath(vector<vector<char>>& grid) {
int m = grid.size(),n = grid[0].size();
vector<vector<vector<bool>>> f(m + 1,vector<vector<bool>>(n + 1,vector<bool>((n + m + 3) / 2,false)));
f[0][1][0] = true;
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
for(int k = 0; k < (n + m + 1) / 2; k++) {
int val = grid[i - 1][j - 1] == '(' ? 1 : -1;
if(k - val >= 0) {
f[i][j][k] = f[i - 1][j][k - val] | f[i][j - 1][k - val];
}
}
}
}
return f[m][n][0];
}
};
// ( = 1 , ) = -1, to get 0, and min(prefix_sum) >= 0
#2
tiansuohaoer2026-09-29
13094
可以bitset加速```
class Solution {
public:
bool hasValidPath(vector<vector<char>>& mp) {
int i,j,n,m;
bitset<105> f[105][105];
n=mp.size(); m=mp[0].size();
f[0][1][0]=1;
for(i=1;i<=n;i++)for(j=1;j<=m;j++){
f[i][j]=(f[i-1][j]|f[i][j-1]);
if(mp[i-1][j-1]=='(')f[i][j]<<=1;
else f[i][j]>>=1;
}
return f[n][m][0];
}
};
#3
o8080x2026-09-29
28632
Kotlin每日打卡（DFS+剪枝）：```
class Solution {
fun hasValidPath(grid: Array<CharArray>): Boolean {
val m = grid.size
val n = grid[0].size
if ((m + n) % 2 == 0 || grid[0][0] == ')' || grid[m - 1][n - 1] == '(') {
return false
}
val vis = Array(m) { Array(n) { BooleanArray((m + n + 1) / 2) } }
return dfs(0, 0, 0, grid, vis)
}
private fun dfs(x: Int, y: Int, count: Int, grid: Array<CharArray>, vis: Array<Array<BooleanArray>>): Boolean {
val m = grid.size
val n = grid[0].size
if (count > m - x + n - y - 1) {
return false
}
if (x == m - 1 && y == n - 1) {
return count == 1
}
if (vis[x][y][count]) {
return false
}
vis[x][y][count] = true
val nextCount = count + if (grid[x][y] == '(') 1 else -1
if (nextCount < 0) {
return false
}
return x < m - 1 && dfs(x + 1, y, nextCount, grid, vis) ||
y < n - 1 && dfs(x, y + 1, nextCount, grid, vis)
}
}
#4
欧拉线2026-09-29
12619
思路：滚动 DP + 位集优化```
#include <stdbool.h>
#include <stdint.h>
#include <string.h>
bool hasValidPath(char** grid, int gridSize, int* gridColSize) {
int m = gridSize, n = gridColSize[0], len = m + n - 1;
if ((len & 1) || grid[0][0] == ')' || grid[m - 1][n - 1] == '(')
return false;
int k = (len / 2 + 64) / 64;
uint64_t dp[n][k], cur[k];
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
for (int t = 0; t < k; ++t)
cur[t] = dp[j][t] | (j ? dp[j - 1][t] : 0);
for (int t = 0; t < k; ++t) {
if (grid[i][j] == '(')
dp[j][t] = (cur[t] << 1) | (t ? cur[t - 1] >> 63 : 0);
else
dp[j][t] =
(cur[t] >> 1) | (t + 1 < k ? cur[t + 1] << 63 : 0);
}
}
}
return (dp[n - 1][0] & 1) != 0;
}
#5
doge2026-09-29
28633
擦车+剪枝提前退出，也可以继续优化成递推dp（但是懒了 ^-^```
class Solution:
def hasValidPath(self, grid: List[List[str]]) -> bool:
m, n = len(grid), len(grid[0])
if (m + n) % 2 == 0 or (grid[0][0] == ')') or (grid[-1][-1] == '('):
return False
@cache
def dfs(i, j, c):
if c > (m - i) + (n - j) - 1:
return False
if i == m - 1 and j == n - 1:
return c == 1
c += 1 if grid[i][j] == '(' else -1
if c < 0:
return False
return (i + 1 < m and dfs(i + 1, j, c)) or \
(j + 1 < n and dfs(i, j + 1, c))
return dfs(0, 0, 0)
#6

发表回复

登录后回复