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

1
class Solution {
2
  static Boolean[][][] dp;
3

4
  public boolean hasValidPath(char[][] grid) {
5
    int m = grid.length, n = grid[0].length;
6
    dp = new Boolean[101][101][201]; // [row][col][open-close]
7
    if (grid[0][0] == ')') { // cannot start with ')'
8
      return false;
9
    }
10
    if (grid[m - 1][n - 1] == '(') { // cannot end with '('
11
      return false;
12
    }
13
    return solve(grid, 0, 0, m, n, 0, 0);
14
  }
15

16
  public static boolean solve(char[][] grid, int i, int j, int m, int n, int open, int close) {
17
    if (grid[i][j] == '(') {
18
      open++;
19
    } else {
20
      close++;
21
    }
22
    if (close
23
        > open) { // at any point if closeBracket count exceeds openBracket count then return false
24
      // since this path can never lead to valid paranthesis string
25
      return false;
26
    }
27
    if (i == m - 1
28
        && j
29
            == n - 1) { // on reaching bottom right cell if openCount == closeCount return true else
30
      // return false
31
      return open == close;
32
    }
33
    if (dp[i][j][open - close] != null) { // check for precomputed overlapping subproblem
34
      return dp[i][j][open - close];
35
    }
36
    if (i == m - 1) { // make sure to not go out of the grid in last row
37
      return dp[i][j][open - close] = solve(grid, i, j + 1, m, n, open, close);
38
    }
39
    if (j == n - 1) { // make sure to not go out of the grid in last col
40
      return dp[i][j][open - close] = solve(grid, i + 1, j, m, n, open, close);
41
    }
42
    boolean op =
43
        solve(grid, i + 1, j, m, n, open, close)
44
            || solve(
45
                grid, i, j + 1, m, n, open,
46
                close); // we have two choices to move forward, [i+1][j] or [i][j+1]
47
    return dp[i][j][open - close] = op;
48
  }
49
}