Formatted question description: https://leetcode.ca/all/2267.html

2267. Check if There Is a Valid Parentheses String Path

Difficulty: Hard.
Related Topics: Array, Dynamic Programming, Matrix.
Similar Questions: Check if There is a Valid Path in a Grid, Check if a Parentheses String Can Be Valid.

Problem

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

Solution

class Solution {
    private char[][] grid;
    private int m;
    private int n;
    private static final char LFTPAR = '(';
    private static final char RGTPAR = ')';

    public boolean hasValidPath(char[][] grid) {
        this.grid = grid;
        this.m = grid.length;
        this.n = grid[0].length;
        Boolean[][][] dp = new Boolean[m][n][m + n + 1];
        if (grid[0][0] == RGTPAR) {
            return false;
        }
        if ((m + n) % 2 == 0) {
            return false;
        }
        return dfs(0, 0, 0, 0, dp);
    }

    private boolean dfs(int u, int v, int open, int close, Boolean[][][] dp) {
        if (grid[u][v] == LFTPAR) {
            open++;
        } else {
            close++;
        }
        if (u == m - 1 && v == n - 1) {
            return open == close;
        }
        if (open < close) {
            return false;
        }
        if (dp[u][v][open - close] != null) {
            return dp[u][v][open - close];
        }
        if (u == m - 1) {
            boolean result = dfs(u, v + 1, open, close, dp);
            dp[u][v][open - close] = result;
            return result;
        }
        if (v == n - 1) {
            return dfs(u + 1, v, open, close, dp);
        }
        boolean rslt;
        if (grid[u][v] == LFTPAR) {
            rslt = dfs(u + 1, v, open, close, dp) || dfs(u, v + 1, open, close, dp);
        } else {
            rslt = dfs(u, v + 1, open, close, dp) || dfs(u + 1, v, open, close, dp);
        }
        dp[u][v][open - close] = rslt;
        return rslt;
    }
}

############

class Solution {
    private boolean[][][] vis;
    private char[][] grid;
    private int m;
    private int n;

    public boolean hasValidPath(char[][] grid) {
        m = grid.length;
        n = grid[0].length;
        this.grid = grid;
        vis = new boolean[m][n][m + n];
        return dfs(0, 0, 0);
    }

    private boolean dfs(int i, int j, int t) {
        if (vis[i][j][t]) {
            return false;
        }
        vis[i][j][t] = true;
        t += grid[i][j] == '(' ? 1 : -1;
        if (t < 0) {
            return false;
        }
        if (i == m - 1 && j == n - 1) {
            return t == 0;
        }
        int[] dirs = {0, 1, 0};
        for (int k = 0; k < 2; ++k) {
            int x = i + dirs[k], y = j + dirs[k + 1];
            if (x < m && y < n && dfs(x, y, t)) {
                return true;
            }
        }
        return false;
    }
}

class Solution:
    def hasValidPath(self, grid: List[List[str]]) -> bool:
        @cache
        def dfs(i, j, t):
            if grid[i][j] == '(':
                t += 1
            else:
                t -= 1
            if t < 0:
                return False
            if i == m - 1 and j == n - 1:
                return t == 0
            for x, y in [(i + 1, j), (i, j + 1)]:
                if x < m and y < n and dfs(x, y, t):
                    return True
            return False

        m, n = len(grid), len(grid[0])
        return dfs(0, 0, 0)

############

# 2267.  Check if There Is a Valid Parentheses String Path
# https://leetcode.com/problems/check-if-there-is-a-valid-parentheses-string-path/

class Solution:
    def hasValidPath(self, grid: List[List[str]]) -> bool:
        if grid[0][0] == ")": return False
        
        rows, cols = len(grid), len(grid[0])
        
        @cache
        def go(x, y, opened):
            if x == rows - 1 and y == cols - 1:
                return opened == 0
            
            def pos(dx, dy):
                if 0 <= dx < rows and 0 <= dy < cols:
                    if grid[dx][dy] == ")":
                        if opened >= 1:
                            return go(dx, dy, opened - 1)
                    else:
                        return go(dx, dy, opened + 1)
                        
                return False
            
            return pos(x + 1, y) or pos(x, y + 1)
        
        return go(0, 0, 1)

bool vis[100][100][200];
int dirs[3] = {1, 0, 1};

class Solution {
public:
    bool hasValidPath(vector<vector<char>>& grid) {
        memset(vis, 0, sizeof(vis));
        return dfs(0, 0, 0, grid);
    }

    bool dfs(int i, int j, int t, vector<vector<char>>& grid) {
        if (vis[i][j][t]) return false;
        vis[i][j][t] = true;
        t += grid[i][j] == '(' ? 1 : -1;
        if (t < 0) return false;
        int m = grid.size(), n = grid[0].size();
        if (i == m - 1 && j == n - 1) return t == 0;
        for (int k = 0; k < 2; ++k) {
            int x = i + dirs[k], y = j + dirs[k + 1];
            if (x < m && y < n && dfs(x, y, t, grid)) return true;
        }
        return false;
    }
};

func hasValidPath(grid [][]byte) bool {
	m, n := len(grid), len(grid[0])
	vis := make([][][]bool, m)
	for i := range vis {
		vis[i] = make([][]bool, n)
		for j := range vis[i] {
			vis[i][j] = make([]bool, m+n)
		}
	}
	var dfs func(int, int, int) bool
	dfs = func(i, j, t int) bool {
		if vis[i][j][t] {
			return false
		}
		vis[i][j][t] = true
		if grid[i][j] == '(' {
			t += 1
		} else {
			t -= 1
		}
		if t < 0 {
			return false
		}
		if i == m-1 && j == n-1 {
			return t == 0
		}
		dirs := []int{1, 0, 1}
		for k := 0; k < 2; k++ {
			x, y := i+dirs[k], j+dirs[k+1]
			if x < m && y < n && dfs(x, y, t) {
				return true
			}
		}
		return false
	}
	return dfs(0, 0, 0)
}

Explain:

nope.

Complexity:

Time complexity : O(n).
Space complexity : O(n).

2267 - Check if There Is a Valid Parentheses String Path

2267. Check if There Is a Valid Parentheses String Path

Problem

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

2267. Check if There Is a Valid Parentheses String Path

Problem

Solution

All Problems

All Solutions