2267.检查是否有合法括号字符串路径：动态规划（bitset记状态）

【LetMeFly】2267.检查是否有合法括号字符串路径：动态规划（bitset记状态）

力扣题目链接：https://leetcode.cn/problems/check-if-there-is-a-valid-parentheses-string-path/

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

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

解题方法：动态规划

创建一个二维数组DP，其中DP[i][j]表示从起点到达位置(i,j)时，所有可能的括号状态。

怎么表示所有的状态？不难发现，我们只需要记录左括号比右括号多几个（不能为负数），使用一个有$m+n+1$位的大整数bitset来表示即可。其中bitset的第$k$位为1则表示到该位置存在左括号比右括号多$k$个的路径。

状态怎么转移？一个位置要么从左边要么从上方来，如果这个位置是(，到其上方为止左括号比右括号可能多$1, 3, 7$个，那么到该位置位置左括号比右括号可能多$2, 4, 8$个，即上方的bitset左移一位。如果这个位置是)，即上方的bitset右移一位。

初始值grid[0][0]如果是(则有dp[0][0]的第1位为1，最终若dp[m-1][n-1]的第0位为1，则说明存在一条路径左右括号数量相等，返回true。

有同学担心)(这种左右括号数量相等但其实不合法的情况怎么办，其实不用担心，遇到)时候左括号比右括号数量多-1个，而bitset没有-1位，相当于这种情况在bitset右移的时候直接给抹掉了。

• 时间复杂度$O(mn \frac{m+n}{W})$，其中$W$是机器字长，现多为64。
• 空间复杂度$O(mn \frac{m+n}{W})$

AC代码

C++

/*
 * @LastEditTime: 2026-09-29 08:53:56
 */
typedef bitset<201> states;
class Solution {
private:
    void modify(states& now, states& from, bool is_more) {
        if (is_more) {
            now |= from << 1;
        } else {
            now |= from >> 1;
        }
    }
public:
    bool hasValidPath(vector<vector<char>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<states>> dp(n, vector<states>(m));
        if (grid[0][0] == ')') {
            return false;
        }
        dp[0][0].set(1);
        vector<array<int, 2>> care_list = {{0, 0}, {0, 1}, {0, 2}, {1, 2}, {2, 2}, {3, 2}};
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                bool is_more = grid[i][j] == '(';
                if (i) {
                    modify(dp[i][j], dp[i - 1][j], is_more);
                }
                if (j) {
                    modify(dp[i][j], dp[i][j - 1], is_more);
                }
            }
        }
        return dp[n - 1][m - 1].test(0);
    }
};

#ifdef _DEBUG
/*
[["(","(","("],[")","(",")"],["(","(",")"],["(","(",")"]]

true
*/
int main() {
    string s;
    while (cin >> s) {
        vector<vector<char>> v = stringToVectorVectorC(s);
        debug(v);
        Solution sol;
        cout << sol.hasValidPath(v) << endl;
    }
    return 0;
}
#endif

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源