We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Check if There Is a Valid Parentheses String Path

Difficulty: Hard

Problem Description

You are given an m x n matrix of parentheses grid. A valid parentheses string path in the grid is a path that starts from the upper left cell (0, 0), ends at the bottom-right cell (m - 1, n - 1), only moves down or right, and forms a valid parentheses string. Return true if there exists a valid parentheses string path in the grid. Otherwise, return false.

Key Insights

  • A valid parentheses string can be constructed only if the number of opening parentheses '(' is greater than or equal to the number of closing parentheses ')' at any point in the path.
  • The path can only move in two directions: down or right.
  • A dynamic programming (DP) approach can be employed to keep track of the valid paths based on the current balance of parentheses.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(m * n)

Solution

The solution involves using a dynamic programming approach to keep track of the valid parentheses balance at each cell in the grid. We can use a 2D boolean array dp where dp[i][j] indicates if there is a valid parentheses string path from the start to cell (i, j). Additionally, we maintain the balance of parentheses as we traverse the grid. The balance is incremented by 1 for each '(' and decremented by 1 for each ')'. A valid path exists if the balance is non-negative at each step and ends at a balance of zero at the bottom-right cell.

Code Solutions

def checkValidStringPath(grid):
    m, n = len(grid), len(grid[0])
    
    if grid[0][0] == ')' or grid[m-1][n-1] == '(':
        return False
    
    dp = [[False] * n for _ in range(m)]
    dp[0][0] = (grid[0][0] == '(')  # Starting point must be '(' to be valid
    
    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0:
                continue
            
            if grid[i][j] == '(':
                if i > 0 and dp[i-1][j]:
                    dp[i][j] = True
                if j > 0 and dp[i][j-1]:
                    dp[i][j] = True
            else:  # grid[i][j] == ')'
                if i > 0 and dp[i-1][j]:
                    dp[i][j] = True
                if j > 0 and dp[i][j-1]:
                    dp[i][j] = True
                
                # Check if balance is valid
                balance = 0
                for x in range(i + 1):
                    for y in range(j + 1):
                        if grid[x][y] == '(':
                            balance += 1
                        else:
                            balance -= 1
                        if balance < 0:
                            break
                    if balance < 0:
                        break
                
                if balance == 0 and dp[i][j]:
                    return True
    
    return dp[m-1][n-1]
← Back to All Questions