2267. Check if There Is a Valid Parentheses String Path

gistfile1.txt

class Solution {
    public boolean hasValidPath(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] ref = new int[m][n];
        
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == '(') {
                    ref[i][j] = 1;
                } else {
                    ref[i][j] = -1;
                }
            }
        }
        
        return dfs(ref, 0, 0, 0, new boolean[m][n][101]);
    }
    
    private boolean dfs(int[][] ref, int i, int j, int sum, boolean[][][] isVisited) {
        if(i >= ref.length || j >= ref[0].length || isVisited[i][j][sum]) return false;
        
        sum += ref[i][j];
        
        int remain = ref.length - i - 1 +  ref[0].length - j - 1;
        
        if(sum < 0 || sum > remain) return false;
        
        isVisited[i][j][sum] = true;
        
        if(i == ref.length - 1 && j == ref[0].length - 1 && sum == 0) {
            return true;
        }
        
        return dfs(ref, i + 1, j, sum, isVisited) || dfs(ref, i, j + 1, sum, isVisited);
    }
}