2267. Check if There Is a Valid Parentheses String Path

1. Description

You receive an m x n grid whose cells contain opening or closing parentheses.
Starting at (0, 0), reach (m - 1, n - 1) by taking only steps to the right or downward. Read each visited cell, including both endpoints, to form a string.
Determine whether at least one such path produces balanced parentheses: every prefix must contain at least as many opening parentheses as closing ones, and their total counts must match.
Return true when such a path exists, and false otherwise.

2. Example

Example 1

Input: grid = [["(","(","("],[")","(",")"],["(","(",")"],["(","(",")"]]
Output: true
Explanation: Paths producing “()(())” and “((()))” both satisfy the requirements.

Example 2

Input: grid = [[")",")"],["(","("]]
Output: false
Explanation: Both routes begin with a closing parenthesis, so neither can be balanced.

3. Constraints

• The grid has m rows and n columns, with 1 <= m, n <= 100.
• Each cell contains either ‘(’ or ‘)’.

4. Solutions

Dynamic Programming && Bit Manipulation

m = grid.size(), n = grid[0].size()
Time complexity: O(mn)
Space complexity: O(n)

The complexities above treat the fixed 250-bit bitset as constant size.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
public:
    bool hasValidPath(const vector<vector<char>> &grid) {
        const int m = grid.size(), n = grid[0].size();

        if ((m + n - 1) % 2 != 0 || grid[0][0] != '(' || grid[m - 1][n - 1] != ')') {
            return false;
        }

        vector<bitset<250>> balance(n);
        balance[0].set(0);

        for (int i = 0; i < m; ++i) {
            if (grid[i][0] == '(') {
                balance[0] <<= 1;
            } else {
                balance[0] >>= 1;
            }

            for (int j = 1; j < n; ++j) {
                bitset<250> current = balance[j] | balance[j - 1];
                if (grid[i][j] == '(') {
                    current <<= 1;
                } else {
                    current >>= 1;
                }

                balance[j] = current;
            }
        }

        return balance.back().test(0);
    }
};