A parentheses string is a non-empty string consisting only of '('
and ')'
. It is valid if any of the following conditions is true:
- It is
()
. - It can be written as
AB
(A
concatenated withB
), whereA
andB
are valid parentheses strings. - It can be written as
(A)
, whereA
is a valid parentheses string.
You are given an m x n
matrix of parentheses grid
. A valid parentheses string path in the grid is a path satisfying all of the following conditions:
- The path starts from the upper left cell
(0, 0)
. - The path ends at the bottom-right cell
(m - 1, n - 1)
. - The path only ever moves down or right.
- The resulting parentheses string formed by the path is valid.
Return true
if there exists a valid parentheses string path in the grid. Otherwise, return false
.
Example 1:
Input: grid = [["(","(","("],[")","(",")"],["(","(",")"],["(","(",")"]] Output: true Explanation: The above diagram shows two possible paths that form valid parentheses strings. The first path shown results in the valid parentheses string "()(())". The second path shown results in the valid parentheses string "((()))". Note that there may be other valid parentheses string paths.
Example 2:
Input: grid = [[")",")"],["(","("]] Output: false Explanation: The two possible paths form the parentheses strings "))(" and ")((". Since neither of them are valid parentheses strings, we return false.
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 100
grid[i][j]
is either'('
or')'
.
Companies: Google
Related Topics:
Array, Dynamic Programming, Matrix
Similar Questions:
- Check if There is a Valid Path in a Grid (Medium)
- Check if a Parentheses String Can Be Valid (Medium)
Hints:
- What observations can you make about the number of open brackets and close brackets for any prefix of a valid bracket sequence?
- The number of open brackets must always be greater than or equal to the number of close brackets.
- Could you use dynamic programming?
// OJ: https://leetcode.com/problems/check-if-there-is-a-valid-parentheses-string-path
// Author: github.com/lzl124631x
// Time: O(MN * (M + N))
// Space: O(MN * (M + N))
class Solution {
public:
bool hasValidPath(vector<vector<char>>& A) {
if (A[0][0] == ')') return false;
int M = A.size(), N = A[0].size();
vector<vector<bitset<100>>> dp(M, vector<bitset<100>>(N));
dp[0][0].set(1);
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (i == 0 && j == 0) continue;
int d = A[i][j] == '(' ? 1 : -1;
if (i - 1 >= 0) {
dp[i][j] |= A[i][j] == '(' ? (dp[i - 1][j] << 1) : (dp[i - 1][j] >> 1);
}
if (j - 1 >= 0) {
dp[i][j] |= A[i][j] == '(' ? (dp[i][j - 1] << 1) : (dp[i][j - 1] >> 1);
}
}
}
return dp[M - 1][N - 1].test(0);
}
};
Since dp[i][j]
only depends on dp[i-1][j]
and dp[i][j-1]
, we can reduce the space complexity to O(N * (M+N))
// OJ: https://leetcode.com/problems/check-if-there-is-a-valid-parentheses-string-path
// Author: github.com/lzl124631x
// Time: O(MN * (M + N))
// Space: O(N * (M + N))
class Solution {
public:
bool hasValidPath(vector<vector<char>>& A) {
if (A[0][0] == ')') return false;
int M = A.size(), N = A[0].size();
vector<bitset<100>> dp(N);
for (int i = 0; i < M; ++i) {
vector<bitset<100>> next(N);
for (int j = 0; j < N; ++j) {
if (i == 0 && j == 0) {
next[0].set(1);
continue;
}
int d = A[i][j] == '(' ? 1 : -1;
if (i - 1 >= 0) {
next[j] |= A[i][j] == '(' ? (dp[j] << 1) : (dp[j] >> 1);
}
if (j - 1 >= 0) {
next[j] |= A[i][j] == '(' ? (next[j - 1] << 1) : (next[j - 1] >> 1);
}
}
swap(dp, next);
}
return dp[N - 1].test(0);
}
};