Check if There Is a Valid Parentheses String Path LeetCode Solution

Problem – Check if There Is a Valid Parentheses String Path LeetCode Solution

A parentheses string is a non-empty string consisting only of '(' and ')'. It is valid if any of the following conditions is true:

  • It is ().
  • It can be written as AB (A concatenated with B), where A and B are valid parentheses strings.
  • It can be written as (A), where A is a valid parentheses string.

You are 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.

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

Check if There Is a Valid Parentheses String Path LeetCode Solution in Java

    public boolean hasValidPath(char[][] A) {
        int m = A.length, n = A[0].length;
        boolean[][][] dp = new boolean[m + 1][n + 1][103];
        dp[0][0][1] = true;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                for (int k = 1; k <= 101; ++k) {
                    dp[i][j + 1][k] |= dp[i][j][k + (A[i][j] == '(' ? -1 : 1)];
                    dp[i + 1][j][k] |= dp[i][j][k + (A[i][j] == '(' ? -1 : 1)];
                }
        return dp[m][n - 1][1];
    }

Check if There Is a Valid Parentheses String Path LeetCode Solution in C++

class Solution {
public:
    bool hasValidPath(vector<vector<char>>& grid) {
        
        queue<tuple<int,int,int>> q;
        int visited[100][100][101] = {};
        
        int row=grid.size();
        int col=grid[0].size();
        
        if(grid[0][0]=='(') q.push({0,0,1});
        else return false;
        
        while(!q.empty()){
            
            auto [Nx,Ny,b]=q.front();
            q.pop();
            
            if(b<0 or b>(row+col)/2 or visited[Nx][Ny][b]) continue;
            visited[Nx][Ny][b] = true;

            if(Nx==row-1 and Ny==col-1 and b==0) return true;
            
            if(Nx+1<row){
                if(grid[Nx+1][Ny]=='(') q.push({Nx+1,Ny,b+1});
                else q.push({Nx+1,Ny,b-1});
            }
            if(Ny+1<col){
                if(grid[Nx][Ny+1]=='(') q.push({Nx,Ny+1,b+1});
                else q.push({Nx,Ny+1,b-1});
            }
            
        }
        return false;
        
    }
};

Check if There Is a Valid Parentheses String Path LeetCode Solution in Python

class Solution:
    def hasValidPath(self, grid: List[List[str]]) -> bool:  
        m = len(grid)
        n = len(grid[0])
        @lru_cache(maxsize=None)
        def hasValidPathInner(x, y, cnt):
            # cnt variable would act as a counter to track 
            # the balance of parantheses sequence
            if x == m or y == n or cnt < 0:
                return False
            
            # logic to check the balance of sequence
            cnt += 1 if grid[x][y] == '(' else -1
            
            # if balanced and end of grid, return True
            if x == m - 1 and y == n - 1 and not cnt:
                return True
            
            return hasValidPathInner(x + 1, y, cnt) or hasValidPathInner(x, y + 1, cnt)

        return hasValidPathInner(0, 0, 0)
Check if There Is a Valid Parentheses String Path LeetCode Solution Review:

In our experience, we suggest you solve this Check if There Is a Valid Parentheses String Path and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Check if There Is a Valid Parentheses String Path LeetCode Solution or any coding solution.

Conclusion:

I hope this Check if There Is a Valid Parentheses String Path LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions

Leave a Reply

Your email address will not be published.