Check if There Is a Valid Parentheses String Path
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(Aconcatenated withB), whereAandBare valid parentheses strings. - It can be written as
(A), whereAis 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
trueThere are paths that form valid parentheses strings such as "()(())" and "((()))".
Example 2
) ) ( (
Input
grid = [[")",")"],["(","("]]Output
falseThe two possible paths form the parentheses strings "))(" and ")((", neither of which is valid.
Constraints
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 100
- grid[i][j] is either '(' or ')'.