2267. Check if There Is a Valid Parentheses String Path

Problem Description

The given problem presents a matrix grid filled with parentheses characters, either '(' or ')'. The task is to determine whether there exists at least one path from the top-left corner of the grid to the bottom-right corner, such that:

• The path only moves downwards or to the right, one cell at a time.
• The sequence of parentheses encountered along the path forms a valid parentheses string.

A parentheses string is considered valid if it meets any of the following conditions:

1. It is an empty string or consists solely of one pair of parentheses: ().
2. It can be divided into two consecutive parts, A and B, both of which are valid parentheses strings themselves.
3. It can be enclosed in a single pair of parentheses, with the inside being a valid parentheses string.

In simpler terms, we must find a path where the order and number of opening '(' and closing ')' parentheses balance each other correctly as specified by the valid parentheses string definition.

Intuition

To find a solution, we use a Depth-First Search (DFS) algorithm combined with memoization to avoid redundant computations for previously visited cell states. The idea is to traverse the grid by moving right or down and tracking the balance of parentheses as follows:

• Increment the balance t whenever an opening parenthesis '(' is encountered.
• Decrement the balance t whenever a closing parenthesis ')' is encountered.

Since we cannot have more closing brackets before opening brackets in a valid parentheses sequence, any path where the balance becomes negative at any point is invalid and can be disregarded. While traversing, if we reach the bottom-right cell and the balance t is zero, we have found a valid path, and we can return true.

Through memoization with @cache, we store the results of subproblems so that we don't recompute the validity of paths from the same cell and with the same current balance t. By trying each possible path and checking the balance of parentheses, we can determine if a valid path exists without exploring every possible permutation exhaustively, thus saving time.

The recursive DFS function dfs(i, j, t) tries to find a path starting from cell (i, j) with a current parentheses balance t. If a valid path is found at any point, the function returns true and concludes early. Otherwise, it exhaustively searches and eventually may return false if no valid paths exist.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution to the problem utilizes a Deep-First Search (DFS) approach that is defined in the function dfs(i, j, t), where i and j represent the current cell's row and column indices in the grid, and t is the current balance of parentheses.

Here's a step-by-step breakdown of how the solution is implemented:

1. Initialization: The function initializes by reading the dimensions of the grid into variables m and n. The DFS function is then called starting from the top-left cell (0, 0) with an initial balance t of 0.

2. DFS Function (dfs(i, j, t)): The core recursive function checks whether the current path is valid as it traverses the grid:

   • Update Balance: We update the balance t by incrementing for an opening parenthesis '(' and decrementing for a closing parenthesis ')'.

   • Invalid Condition: If the balance t is negative, we stop exploration down this path because more closing parentheses than opening ones have been encountered, making the path invalid.

   • Base Case - Target Cell: If the current cell is the bottom-right cell (m - 1, n - 1), we check if t is 0. A balance of zero means we have an equal number of opening and closing parentheses, indicating a valid path.

   • Recursive Exploration: For a non-terminating cell, the function branches by calling itself for the next cell to the right (i, j + 1) or the next cell down (i + 1, j), if those cells are within the bounds of the grid. This continues until the base case or invalid condition is met.

3. Memoization: The function is decorated with the @cache decorator from Python's functools library, which memoizes the results. This means that for a given state (i, j, t), subsequent DFS calls with the same state will return the memoized result instead of recomputing. This optimizes the DFS algorithm’s efficiency and reduces the overall time complexity.

4. Returning Result: The initial call to dfs(0, 0, 0) will eventually return true or false based on whether a valid path is found. This value is then returned by the hasValidPath method.

The solution wisely combines a DFS traversal to explore paths through the grid, a balance tracker to ensure valid parentheses structure, and memoization to avoid redundant calculations for paths already explored with a given balance. By employing these algorithms and patterns, the solution effectively returns true if there exists at least one valid parenthesis path in the grid, or false otherwise.

Example Walkthrough

Let's illustrate the solution approach with an example. Consider the following grid:

1grid = [
2  "(()",
3  "())",
4  "())"
5]

We want to find at least one path from the top-left corner to the bottom-right corner, where the sequence of parentheses forms a valid string. Here is how we might apply the solution approach outlined previously:

1. Initialization: We start at the top-left corner of the grid at cell (0, 0) and an initial balance t of 0.

2. Recursive DFS Exploration:

   • Start at (0, 0) with character '(' which increments the balance t to 1.
   • Move right to (0, 1) encountering another '(', now balance is 2.
   • Next, at (0, 2), we encounter ')', and balance decrements to 1.
   • Now we can only go down to (1, 2). Here we find ')' again, so balance decrements to 0.
   • From (1, 2), we can only move down to (2, 2). The character here is ')', which would decrement the balance to -1.

   At this point, the path goes invalid because the balance t becomes negative, so this path is abandoned.

3. Backtracking: We backtrack to the last valid cell (1, 2) with balance 0 and attempt another path:

   • Move up one cell to (0, 2) and then left to (0, 1), looping back to a previously visited state, but this time with an invalid balance due to the path we've taken. This path is abandoned.

4. Exploring Alternative Paths:

   • Start over at (0, 0) this time going downwards.
   • Move down to (1, 0) encountering ')', which decrements the balance to 0.
   • Next, we move right to (1, 1) and get '(', now balance is 1.
   • Moving right again to (1, 2), we find ')', so balance goes to 0.
   • Now, go down to (2, 2). The balance is valid at 0, but we have found that this cell will lead to an invalid path from our previous exploration.

The algorithm continues exploring alternative paths by stepping through the grid, updating balances, backtracking upon invalid paths, and attempting new pathways until it eventually finds a valid path or exhausts all possibilities.

5. Memoization: Throughout this process, the algorithm has been storing the resulting state of each cell and current balance in memory, ensuring that any repeat visits to the same state do not require re-computation. This significantly reduces the amount of work needed.

6. Returning Result: It turns out there's no valid path from the top-left to the bottom-right cell in our example, so the hasValidPath call would return false.

This example illustrates the recursive and backtrack nature of the DFS approach with memoization by trying different paths and checking the balance of parentheses until a valid or no path is found.

Solution Implementation

Time and Space Complexity

The given Python code defines a method hasValidPath which determines if there is a valid path from the upper left corner to the lower right corner in a grid, following certain rules related to parentheses balance. The algorithm uses Depth First Search (DFS) with memoization to explore possible paths.

Time Complexity:

The time complexity of the DFS is potentially O(2^(m+n)) without memoization, since in the worst case, each cell has two choices (to go right or down) and could be visited multiple times. However, with memoization, each unique state is computed only once. A state is defined by the current position (i, j) and the current balance t of parentheses. Since i can take m values, j can take n values, and t can range from -n to m (since the path is invalid if the balance is outside this range), the number of unique states is O(m * n * (m+n)).

Therefore, t can have maximum m + n + 1 valid different values (from 0 to m + n), so the time complexity is O(m * n * (m+n)).

Space Complexity:

For space complexity, we have:

1. The recursive stack space, which in the worst-case scenario can grow as deep as m + n (the length of the longest path from (0, 0) to (m-1, n-1)). This contributes O(m + n) to the space complexity.
2. The cache that memoizes the states to avoid re-computing the same state. This cache could be at most m * n * (m+n) in size, as analyzed before, which makes it O(m * n * (m+n)).

Thus, the space complexity is primarily determined by the size of the memoization cache and the recursive call stack. The resulting total space complexity of the algorithm is O(m * n * (m+n)).

Learn more about how to find time and space complexity quickly using problem constraints.