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

Master LeetCode problem 2267 ( Check if There Is a Valid Parentheses String Path), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2267. Check if There Is a Valid Parentheses String Path

Hard

Array Dynamic Programming Matrix

Problem Explanation

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:

Start DFS from the top-left cell (0, 0) with initial counts of open and closed parentheses as 0.
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 ')'.
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 ')'.
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.
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. :

Solution Code

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;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2267 ( Check if There Is a Valid Parentheses String Path)?

This page provides optimized solutions for LeetCode problem 2267 ( Check if There Is a Valid Parentheses String Path) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2267 ( Check if There Is a Valid Parentheses String Path)?

The time complexity for LeetCode 2267 ( Check if There Is a Valid Parentheses String Path) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2267 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2267 in Java, C++, or Python.

Back to LeetCode Solutions