Skip to content

2267. Check if There Is a Valid Parentheses String Path 👍

  • Time: $O(mn(m + n))$
  • Space: $O(mn(m + n))$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
 public:
  bool hasValidPath(vector<vector<char>>& grid) {
    const int m = grid.size();
    const int n = grid[0].size();
    vector<vector<vector<int>>> mem(
        m, vector<vector<int>>(n, vector<int>(m + n, -1)));
    return hasValidPath(grid, 0, 0, 0, mem);
  }

 private:
  // Returns true if there's a path from grid[i][j] to grid[m - 1][n - 1], where
  // the number of '(' - the number of ')' == k.
  bool hasValidPath(const vector<vector<char>>& grid, int i, int j, int k,
                    vector<vector<vector<int>>>& mem) {
    if (i == grid.size() || j == grid[0].size())
      return false;
    k += grid[i][j] == '(' ? 1 : -1;
    if (k < 0)
      return false;
    if (i == grid.size() - 1 && j == grid[0].size() - 1)
      return k == 0;
    if (mem[i][j][k] != -1)
      return mem[i][j][k];
    return mem[i][j][k] = hasValidPath(grid, i + 1, j, k, mem) |
                          hasValidPath(grid, i, j + 1, k, mem);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
  public boolean hasValidPath(char[][] grid) {
    final int m = grid.length;
    final int n = grid[0].length;
    Boolean[][][] mem = new Boolean[m][n][m + n];
    return hasValidPath(grid, 0, 0, 0, mem);
  }

  // Returns true if there's a path from grid[i][j] to grid[m - 1][n - 1], where
  // the number of '(' - the number of ')' == k.
  private boolean hasValidPath(char[][] grid, int i, int j, int k, Boolean[][][] mem) {
    if (i == grid.length || j == grid[0].length)
      return false;
    k += grid[i][j] == '(' ? 1 : -1;
    if (k < 0)
      return false;
    if (i == grid.length - 1 && j == grid[0].length - 1)
      return k == 0;
    if (mem[i][j][k] != null)
      return mem[i][j][k];
    return mem[i][j][k] = hasValidPath(grid, i + 1, j, k, mem) | //
                          hasValidPath(grid, i, j + 1, k, mem);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def hasValidPath(self, grid: list[list[str]]) -> bool:
    @functools.lru_cache(None)
    def dp(i: int, j: int, k: int) -> bool:
      """
      Returns True if there's a path from grid[i][j] to grid[m - 1][n - 1],
      where the number of '(' - the number of ')' == k.
      """
      if i == len(grid) or j == len(grid[0]):
        return False
      k += 1 if grid[i][j] == '(' else -1
      if k < 0:
        return False
      if i == len(grid) - 1 and j == len(grid[0]) - 1:
        return k == 0
      return dp(i + 1, j, k) | dp(i, j + 1, k)

    return dp(0, 0, 0)