LeetCode 6059. 检查是否有合法括号字符串路径（BFS）

• • 1. 题目
  • 2. 解题

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/check-if-there-is-a-valid-parentheses-string-path
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

• 使用队列进行广度优先搜索
• 队列里存储 { 待配对的左括号个数，位置信息x， y }，将3个值编码成一个 int

class Solution {
public:
    bool hasValidPath(vector>& grid) {
        int dd = 128*128, d = 128, m = grid.size(), n = grid[0].size();
        if(grid[0][0]!='(' || grid[m-1][n-1]!=')') return false;
        vector> dir = {{0, 1}, {1, 0}};
        queue q;
        unordered_set vis;
        q.push(dd);  // 起点的编码：左括号个数*128*128 + x*128 + y
        vis.insert(dd);
        while(!q.empty())
        {
            auto tp = q.front();
            q.pop();
            int left = tp/dd;
            int x = tp%dd/d, y = tp%d;
            if(x==m-1 && y==n-1 && left==0) return true;
            for(int k = 0; k < 2; ++k)
            {
                int nx = x + dir[k][0], ny = y + dir[k][1];
                if(nx>=0 && nx=0 && ny
                    if(grid[nx][ny]=='(')
                    {
                        int hash = (left+1)*dd+(nx*d+ny);
                        if(!vis.count(hash) && left+1 <= (m-1-nx+n-1-ny))
                        {
                            q.push(hash);
                            vis.insert(hash);
                        }
                    }
                    else
                    {
                        if(left-1 < 0)  // 不能配对
                            continue;
                        int hash = (left-1)*dd+(nx*d+ny);
                        if(!vis.count(hash) && left-1 <= (m-1-nx+n-1-ny))
                        {
                            q.push(hash);
                            vis.insert(hash);
                        }
                    }
                }
            }
        }
        return false;
    }
};

1556 ms 282.6 MB C++

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！