Original Summary

力扣 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; } } 1 个帖子 - 1 位参与者 阅读完整话题

  • 情报分类：综合情报
  • 分类依据：内容未命中明确的垂直分类规则，归入综合情报
  • 信息来源：服务器 / LINUX DO - 最新话题
  • 发布时间：2026/9/29 09:57:05