#2267
Check if There Is a Valid Parentheses String Path
master · 1700 · lc hard +32 · verified · 40.1% accepted · 541 likes · top 19%
Description
A parentheses string is non-empty and consists only of '(' and ')'. It is valid when:
- It is ().
- It is the concatenation AB of two valid strings.
- It is (A) for some valid string A.
You are given an m x n character matrix grid of parentheses. A valid parentheses string path satisfies:
- It begins at (0, 0).
- It ends at (m - 1, n - 1).
- Movement is restricted to right or down.
- The characters along the path form a valid parentheses string.
Return true if such a path exists, 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.
Code
1
2
3