Check if there is a valid parentheses string path
- Array
- Dynamic Programming
- Matrix
- Bracket Sequences
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.
Solution
class Solution:
def hasValidPath(self, grid: list[list[str]]) -> bool:
m, n = len(grid), len(grid[0])
@cache
def solve(i, j, opened):
if i >= m or j >= n:
return False
if grid[i][j] == "(":
opened += 1
else:
opened -= 1
if opened < 0:
return False
if i == m - 1 and j == n - 1:
return not opened
for dx, dy in (0, 1), (1, 0):
if solve(i+dx, j+dy, opened):
return True
return False
return solve(0, 0, 0)