2267. 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.

class Solution {
    int dp[101][101][202];
    int helper(vector<vector<char>>& g, int y, int x, int k, int& n, int& m) {
        if(y >= n or x >= m or k < 0) return 0;
        if(dp[y][x][k] != -1) return dp[y][x][k];
        int nk = k + (g[y][x] == '(' ? 1 : -1);
        int& res = dp[y][x][k] = 0;
        return res = max(helper(g,y+1,x,nk,n,m), helper(g,y,x+1,nk,n,m)); 
    }
public:
    bool hasValidPath(vector<vector<char>>& grid) {
        int n = grid.size(), m = grid[0].size();
        if(grid[0][0] == ')' or grid[n-1][m-1] == '(') return false;
        memset(dp, -1, sizeof dp);
        dp[n - 1][m - 1][1] = true;
        
        return helper(grid, 0, 0, 0, n, m);
    }
};