#2267

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Check if There Is a Valid Parentheses String Path

Check if there exists a valid parentheses string path in a given grid using state transition dynamic programming.

Problem Statement

You are given an m x n matrix consisting of only '(' and ')'. A valid parentheses string is one where every opening bracket '(' has a matching closing bracket ')'. Your task is to determine if there exists a valid path in this grid that forms a valid parentheses string.

A path starts from any cell and can move to adjacent cells (up, down, left, or right). A valid parentheses string path must adhere to the rule that at no point does the number of closing brackets exceed the number of opening brackets. If such a path exists, return true; otherwise, return false.

Examples

Example 1

Input: grid = [["(","(","("],[")","(",")"],["(","(",")"],["(","(",")"]]

Output: true

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

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 ')'.

Solution Approach

State Transition Dynamic Programming

Use dynamic programming to track the balance of parentheses as you traverse the grid. For each cell, maintain a state representing the number of open and close parentheses encountered. The state transition ensures the parentheses balance is valid at every step of the path.

Grid Traversal with Memoization

Memoize the results of the state transitions for each grid cell to avoid redundant calculations. This helps in reducing time complexity while checking for valid paths by ensuring each cell is processed only once with valid transitions.

Path Validation via Prefix Checking

At each step, validate if the number of opening parentheses exceeds the number of closing parentheses. The path is valid if no prefix has more closing than opening brackets. Use this to ensure the path respects the valid parentheses structure.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time and space complexity of the solution depend on the size of the grid (m x n). The DP approach processes each cell in the grid, leading to a time complexity of O(m * n). Space complexity can be optimized to O(m * n) as well by storing intermediate results for memoization and state transitions.

What Interviewers Usually Probe

Can the candidate identify the need for dynamic programming to handle the state transitions effectively?
Do they recognize the importance of validating prefixes to maintain the balance of parentheses?
Can they explain the significance of memoization in reducing redundant calculations for optimal performance?

Common Pitfalls or Variants

Common pitfalls

Failing to track parentheses balance properly, leading to invalid paths.
Not considering all possible directions (up, down, left, right) during grid traversal.
Overlooking the importance of memoization, which could lead to excessive time complexity.

Follow-up variants

Consider implementing this solution for grids containing other types of characters or constraints.
Explore how the solution changes when diagonal movement is allowed in the grid.
Try optimizing the solution with additional techniques like depth-first search (DFS) combined with dynamic programming.

FAQ

What is the primary pattern used in "Check if There Is a Valid Parentheses String Path"?

The problem uses state transition dynamic programming to track parentheses balance while traversing the grid.

How do I efficiently traverse the grid for valid parentheses paths?

You can traverse the grid by checking the balance of parentheses at each step, using dynamic programming and memoization to store intermediate results.

What happens if I do not use memoization in this problem?

Without memoization, your solution may repeatedly calculate the same results, leading to higher time complexity and slower performance.

What are some common mistakes when solving this problem?

Common mistakes include not tracking the parentheses balance correctly, failing to consider all valid directions for movement, and not using memoization effectively.

How does this problem relate to other dynamic programming grid problems?

This problem shares similarities with other grid-based dynamic programming problems, such as those that involve pathfinding or maintaining a state during traversal, where balancing state transitions is crucial.

terminal

Solution

Solution 1: DFS + Pruning

Let $m$ be the number of rows and $n$ be the number of columns in the matrix.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def hasValidPath(self, grid: List[List[str]]) -> bool:
        @cache
        def dfs(i: int, j: int, k: int) -> bool:
            d = 1 if grid[i][j] == "(" else -1
            k += d
            if k < 0 or k > m - i + n - j:
                return False
            if i == m - 1 and j == n - 1:
                return k == 0
            for a, b in pairwise((0, 1, 0)):
                x, y = i + a, j + b
                if 0 <= x < m and 0 <= y < n and dfs(x, y, k):
                    return True
            return False

        m, n = len(grid), len(grid[0])
        if (m + n - 1) % 2 or grid[0][0] == ")" or grid[m - 1][n - 1] == "(":
            return False
        return dfs(0, 0, 0)

Continue Practicing

#2304 minimum path cost in a grid #2328 number of increasing paths in a grid #2435 paths in matrix whose sum is divisible by k