Check if There Is a Valid Parentheses String Path LeetCode solution in C++

1
class Solution {
2
 public:
3
  int n, m;
4
  int dp[101][101][200];
5
  bool find(vector<vector<char>> &mat, int row, int col, int open) {
6
    if (row < 0 || col < 0 || row >= n || col >= m || open < 0) {
7
      return false;
8
    }
9
    if (dp[row][col][open] != -1) {
10
      return dp[row][col][open];
11
    }
12
    if (row == n - 1 && col == m - 1) {
13
      if (mat[row][col] == '(') {
14
        open++;
15
      } else {
16
        open--;
17
      }
18
      return open == 0;
19
    }
20
    if (mat[row][col] == '(') {
21
      if (find(mat, row + 1, col, open + 1) || find(mat, row, col + 1, open + 1)) {
22
        return true;
23
      }
24
    } else {
25
      if (find(mat, row + 1, col, open - 1) || find(mat, row, col + 1, open - 1)) {
26
        return true;
27
      }
28
    }
29
    return dp[row][col][open] = false;
30
  }
31
  bool hasValidPath(vector<vector<char>> &mat) {
32
    memset(dp, -1, sizeof(dp));
33
    n = mat.size();
34
    m = mat[0].size();
35
    return find(mat, 0, 0, 0);
36
  }
37
};