LeetCode 2267: Check if There Is a Valid Parentheses String Path

Explanation:

To solve this problem, we can use a depth-first search (DFS) algorithm to explore all possible paths from the top-left cell to the bottom-right cell in the grid. At each step, we need to make sure that we are forming a valid parentheses string path. We can keep track of the count of open parentheses '(', closed parentheses ')', and the current direction (right or down) while exploring the path.

Algorithm:

1. Start DFS from the top-left cell (0, 0) with initial counts of open and closed parentheses as 0.
2. At each cell, if moving right, increment the count of open parentheses if the current cell is '(', or increment the count of closed parentheses if the current cell is ')'.
3. If moving down, increment the count of open parentheses if the current cell is '(', or increment the count of closed parentheses if the current cell is ')'.
4. If the count of closed parentheses ever exceeds the count of open parentheses or either of the counts exceeds the total possible count from the current cell to the bottom-right cell, return false as it is not a valid parentheses string path.
5. If the DFS reaches the bottom-right cell and the counts of open and closed parentheses are equal, return true.

Time Complexity:

The time complexity of this algorithm is O(m * n) where m is the number of rows and n is the number of columns in the grid.

Space Complexity:

The space complexity is O(m * n) for the recursive stack space in DFS. :

class Solution {
    public boolean hasValidPath(char[][] grid) {
        return dfs(grid, 0, 0, 0, 0);
    }
    
    private boolean dfs(char[][] grid, int i, int j, int open, int closed) {
        if (i == grid.length || j == grid[0].length || closed > open || open > (grid.length - i - 1 + grid[0].length - j - 1)) {
            return false;
        }
        
        if (i == grid.length - 1 && j == grid[0].length - 1) {
            return open == closed;
        }
        
        if ((grid[i][j] == '(' && dfs(grid, i, j + 1, open + 1, closed)) ||
            (grid[i][j] == ')' && dfs(grid, i, j + 1, open, closed + 1)) ||
            (grid[i][j] == '(' && dfs(grid, i + 1, j, open + 1, closed)) ||
            (grid[i][j] == ')' && dfs(grid, i + 1, j, open, closed + 1))) {
            return true;
        }
        
        return false;
    }
}