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

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

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

字符串是 () 。
字符串可以表示为 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 { public: bool hasValidPath(vector<vector<char>>& grid) { } };

rust 解法, 执行用时: 344 ms, 内存消耗: 5.8 MB, 提交时间: 2023-09-14 00:50:20

impl Solution {
    pub fn has_valid_path(grid: Vec<Vec<char>>) -> bool {
        use std::collections::HashSet;
        let mut dp:Vec<Vec<HashSet<i32>>> = vec![vec![HashSet::new();grid[0].len()];grid.len()];

        for (i, row) in grid.iter().enumerate() {
            for (j, cel) in row.iter().enumerate(){
                let inc = if *cel == '(' {1} else {-1};
                let mut cur =HashSet::new();
                if i == 0 && j == 0 {
                    if inc == -1 {return false;}
                    cur.insert(inc);
                }
                if i > 0 {
                    dp[i-1][j].iter().map(|&t| t+inc).filter(|&x| x>=0).for_each(|x| {let _ = cur.insert(x);});
                }
                if j > 0{
                    dp[i][j-1].iter().map(|&t| t+inc).filter(|&x| x>=0).for_each(|x| {let _ = cur.insert(x);});
                }
                dp[i][j] = cur;
            }
        }
        dp.last().unwrap().last().unwrap().contains(&0)
    }
}

golang 解法, 执行用时: 8 ms, 内存消耗: 6.7 MB, 提交时间: 2023-09-14 00:50:02

func hasValidPath(grid [][]byte) bool {
	m, n := len(grid), len(grid[0])
	if (m+n)%2 == 0 || grid[0][0] == ')' || grid[m-1][n-1] == '(' { // 剪枝
		return false
	}

	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+1)/2)
		}
	}
	var dfs func(x, y, c int) bool
	dfs = func(x, y, c int) bool {
		if c > m-x+n-y-1 { // 剪枝：即使后面都是 ')' 也不能将 c 减为 0
			return false
		}
		if x == m-1 && y == n-1 { // 终点
			return c == 1 // 终点一定是 ')'
		}
		if vis[x][y][c] { // 重复访问
			return false
		}
		vis[x][y][c] = true
		if grid[x][y] == '(' {
			c++
		} else if c--; c < 0 { // 非法括号字符串
			return false
		}
		return x < m-1 && dfs(x+1, y, c) || y < n-1 && dfs(x, y+1, c) // 往下或者往右
	}
	return dfs(0, 0, 0) // 起点
}

cpp 解法, 执行用时: 36 ms, 内存消耗: 14.5 MB, 提交时间: 2023-09-14 00:49:49

class Solution {
public:
    bool hasValidPath(vector<vector<char>> &grid) {
        int m = grid.size(), n = grid[0].size();
        if ((m + n) % 2 == 0 || grid[0][0] == ')' || grid[m - 1][n - 1] == '(') return false; // 剪枝
        bool vis[m][n][(m + n + 1) / 2]; memset(vis, 0, sizeof(vis));
        function<bool(int, int, int)> dfs = [&](int x, int y, int c) -> bool {
            if (c > m - x + n - y - 1) return false; // 剪枝：即使后面都是 ')' 也不能将 c 减为 0
            if (x == m - 1 && y == n - 1) return c == 1; // 终点一定是 ')'
            if (vis[x][y][c]) return false; // 重复访问
            vis[x][y][c] = true;
            c += grid[x][y] == '(' ? 1 : -1;
            return c >= 0 && (x < m - 1 && dfs(x + 1, y, c) || y < n - 1 && dfs(x, y + 1, c)); // 往下或者往右
        };
        return dfs(0, 0, 0);
    }
};

java 解法, 执行用时: 4 ms, 内存消耗: 44.4 MB, 提交时间: 2023-09-14 00:49:37

class Solution {
    int m, n;
    char[][] grid;
    boolean[][][] vis;

    public boolean hasValidPath(char[][] grid) {
        m = grid.length;
        n = grid[0].length;
        if ((m + n) % 2 == 0 || grid[0][0] == ')' || grid[m - 1][n - 1] == '(') return false; // 剪枝
        this.grid = grid;
        vis = new boolean[m][n][(m + n + 1) / 2];
        return dfs(0, 0, 0);
    }

    boolean dfs(int x, int y, int c) {
        if (c > m - x + n - y - 1) return false; // 剪枝：即使后面都是 ')' 也不能将 c 减为 0
        if (x == m - 1 && y == n - 1) return c == 1; // 终点一定是 ')'
        if (vis[x][y][c]) return false; // 重复访问
        vis[x][y][c] = true;
        c += grid[x][y] == '(' ? 1 : -1;
        return c >= 0 && (x < m - 1 && dfs(x + 1, y, c) || y < n - 1 && dfs(x, y + 1, c)); // 往下或者往右
    }
}

python3 解法, 执行用时: 300 ms, 内存消耗: 18.5 MB, 提交时间: 2023-09-14 00:49:26

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[m - 1][n - 1] == '(': return False  # 剪枝

        @cache  # 效果类似 vis 数组
        def dfs(x: int, y: int, c: int) -> bool:
            if c > m - x + n - y - 1: return False  # 剪枝：即使后面都是 ')' 也不能将 c 减为 0
            if x == m - 1 and y == n - 1: return c == 1  # 终点一定是 ')'
            c += 1 if grid[x][y] == '(' else -1
            return c >= 0 and (x < m - 1 and dfs(x + 1, y, c) or y < n - 1 and dfs(x, y + 1, c))  # 往下或者往右
        return dfs(0, 0, 0)  # 起点

上一题

下一题

详情