Check if There Is a Valid Parentheses String Path | Leetcode 2267 | Simple DFS | Live coding session

Here is the solution to "Check if There Is a Valid Parentheses String Path" leetcode question. Hope you have a great time going through it.

🎉 Chapters
0:00 Introduction
1:30 Building the algoritm
4:30 Coding it up Solution

🔥🔥🔥🔥👇👇👇 For discussion/feedback/humour/doubts/new openings

👉 Solutions

🔥🔥🔥🔥👇👇👇 For discussion/feedback/humour/doubts/new openings

🔴 Checkout the series: 🔥🔥🔥

🔥🔥🔥 Leetcode Monthly Contest Playlist

PS : Please increase the speed to 1.25X

[devanshsrivastava]

Please explain how the 3-d visited array is functioning?

[ankitghosh]

class Solution {
public:

bool grid) {
int m = grid.size();
int n = grid[0].size();
vector<vector<vector<int>>> vis(m, vector<vector<int>>(n, vector<int>(m+n+1, -1)));
return dfs(grid, 0, 0, 0, vis);
}


bool dfs(vector<vector<char>>& grid, int i, int j, int balance, vector<vector<vector<int>>>& vis){
int m = grid.size();
int n = grid[0].size();
if(i<0 || j<0 || i>=m || j>=n || balance <0)return false;

vis[i][j][balance];

int upbal = balance + ( grid[i][j] == '(' ? 1 : -1);

if(i == m-1 && j == n-1 && upbal == 0)return true;

bool valid = dfs(grid, i+1, j, balance, vis) || dfs(grid, i, j+1, balance, vis);

vis[i][j][balance] = valid;

return valid;
}
};
I am not getting what is wrong here....can u please help?

[sagarbora]

Hi sunchit sr
First and foremost thanks for your valuable time to upload such valuable content
I wanna ask at the worst case how max path will be m+n
If we consider worst case when we have a matrix full of all '('