Loading problem…
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 with B), where A and B are valid parentheses strings. - It can be written as (A), where A 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: Moving only down and right, one path spells "()(())", which is a valid parentheses string, so the answer is true.
Example 2
Input: grid = [[")",")"],["(","("]]
Output: false
Explanation: The only two down/right paths spell "))(" and ")((", and neither is a valid parentheses string, so the answer is false.
Example 3
Input: grid = [["(",")"]]
Output: true
Explanation: There is a single path and it reads "()", which is valid, so the answer is true.
Track, for every cell, the set of open-paren balances reachable by a down/right path whose every prefix stays non-negative; a valid path exists iff balance 0 is reachable at the bottom-right cell.
Run checks all cases above. Submit evaluates all test cases.