2267. Check if There Is a Valid Parentheses String Path LeetCode Solution
In this guide, you will get 2267. Check if There Is a Valid Parentheses String Path LeetCode Solution with the best time and space complexity. The solution to Check if There Is a Valid Parentheses String Path problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Check if There Is a Valid Parentheses String Path
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.
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 ')'.
Complexity Analysis
Time Complexity: O(mn(m + n))
Space Complexity: O(mn(m + n))
2267. Check if There Is a Valid Parentheses String Path LeetCode Solution in C++
class Solution {
public:
bool hasValidPath(vector<vector<char>>& grid) {
const int m = grid.size();
const int n = grid[0].size();
vector<vector<vector<int>>> mem(
m, vector<vector<int>>(n, vector<int>(m + n, -1)));
return hasValidPath(grid, 0, 0, 0, mem);
}
private:
// Returns true if there's a path from grid[i][j] to grid[m - 1][n - 1], where
// the number of '(' - the number of ')' == k.
bool hasValidPath(const vector<vector<char>>& grid, int i, int j, int k,
vector<vector<vector<int>>>& mem) {
if (i == grid.size() || j == grid[0].size())
return false;
k += grid[i][j] == '(' ? 1 : -1;
if (k < 0)
return false;
if (i == grid.size() - 1 && j == grid[0].size() - 1)
return k == 0;
if (mem[i][j][k] != -1)
return mem[i][j][k];
return mem[i][j][k] = hasValidPath(grid, i + 1, j, k, mem) |
hasValidPath(grid, i, j + 1, k, mem);
}
}; /* code provided by PROGIEZ */
2267. Check if There Is a Valid Parentheses String Path LeetCode Solution in Java
class Solution {
public boolean hasValidPath(char[][] grid) {
final int m = grid.length;
final int n = grid[0].length;
Boolean[][][] mem = new Boolean[m][n][m + n];
return hasValidPath(grid, 0, 0, 0, mem);
}
// Returns true if there's a path from grid[i][j] to grid[m - 1][n - 1], where
// the number of '(' - the number of ')' == k.
private boolean hasValidPath(char[][] grid, int i, int j, int k, Boolean[][][] mem) {
if (i == grid.length || j == grid[0].length)
return false;
k += grid[i][j] == '(' ? 1 : -1;
if (k < 0)
return false;
if (i == grid.length - 1 && j == grid[0].length - 1)
return k == 0;
if (mem[i][j][k] != null)
return mem[i][j][k];
return mem[i][j][k] = hasValidPath(grid, i + 1, j, k, mem) | //
hasValidPath(grid, i, j + 1, k, mem);
}
} // code provided by PROGIEZ
2267. Check if There Is a Valid Parentheses String Path LeetCode Solution in Python
class Solution:
def hasValidPath(self, grid: list[list[str]]) -> bool:
@functools.lru_cache(None)
def dp(i: int, j: int, k: int) -> bool:
"""
Returns True if there's a path from grid[i][j] to grid[m - 1][n - 1],
where the number of '(' - the number of ')' == k.
"""
if i == len(grid) or j == len(grid[0]):
return False
k += 1 if grid[i][j] == '(' else -1
if k < 0:
return False
if i == len(grid) - 1 and j == len(grid[0]) - 1:
return k == 0
return dp(i + 1, j, k) | dp(i, j + 1, k)
return dp(0, 0, 0) # code by PROGIEZ
