Check If there is a Valid Parenthesis String Path

In this tutorial, we will solve the Valid Parentheses Path problem using two different approaches: brute force and optimized. We will provide the implementation of the solution in C++, Java, and Python.

Problem Description

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.

Examples

Example 1:

Input: grid = [["(","(","("],[")","(",")"],["(","(",")"],["(","(",")"]]
Output: true
Explanation: 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
Explanation: 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 for Valid Parentheses Path Problem

Intuition and Approach

The problem can be solved using a brute force approach or an optimized approach. The brute force approach directly explores all possible paths, while the optimized approach uses dynamic programming to efficiently check valid paths.

• Brute Force
• Optimized

Approach 1: Brute Force (Naive)

The brute force approach recursively explores all possible paths from the top-left to the bottom-right cell, ensuring the parentheses string remains valid.

Code in Different Languages

C++

Written by @ImmidiSivani

class Solution {
public:
    bool isValidPath(vector<vector<char>>& grid, int i, int j, int balance) {
        if (i >= grid.size() || j >= grid[0].size() || balance < 0) return false;
        balance += (grid[i][j] == '(') ? 1 : -1;
        if (i == grid.size() - 1 && j == grid[0].size() - 1) return balance == 0;
        return isValidPath(grid, i + 1, j, balance) || isValidPath(grid, i, j + 1, balance);
    }
    
    bool hasValidPath(vector<vector<char>>& grid) {
        return isValidPath(grid, 0, 0, 0);
    }
};

Java

Written by @ImmidiSivani

class Solution {
    public boolean isValidPath(char[][] grid, int i, int j, int balance) {
        if (i >= grid.length || j >= grid[0].length || balance < 0) return false;
        balance += (grid[i][j] == '(') ? 1 : -1;
        if (i == grid.length - 1 && j == grid[0].length - 1) return balance == 0;
        return isValidPath(grid, i + 1, j, balance) || isValidPath(grid, i, j + 1, balance);
    }
    
    public boolean hasValidPath(char[][] grid) {
        return isValidPath(grid, 0, 0, 0);
    }
}

Python

Written by @ImmidiSivani

class Solution:
    def isValidPath(self, grid: List[List[str]], i: int, j: int, balance: int) -> bool:
        if i >= len(grid) or j >= len(grid[0]) or balance < 0:
            return False
        balance += 1 if grid[i][j] == '(' else -1
        if i == len(grid) - 1 and j == len(grid[0]) - 1:
            return balance == 0
        return self.isValidPath(grid, i + 1, j, balance) or self.isValidPath(grid, i, j + 1, balance)
    
    def hasValidPath(self, grid: List[List[str]]) -> bool:
        return self.isValidPath(grid, 0, 0, 0)

Complexity Analysis

• Time Complexity: Exponential due to exploring all paths.
• Space Complexity: Exponential due to recursive call stack.
• The brute force approach is inefficient for larger grids.

---

Authors:

Loading...