Question

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

English Version

题目描述

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

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

解法

方法一：记忆化搜索

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)
}