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();
    // dp[i][j][k] := 1 if there's a path from grid[i][j] to grid[m - 1][n - 1]
    // w/ # of '(' - # of ')' == k
    dp.resize(m, vector<vector<int>>(n, vector<int>(m + n, -1)));
    return hasValidPath(grid, 0, 0, 0);
  }

 private:
  vector<vector<vector<int>>> dp;

  int hasValidPath(const vector<vector<char>>& grid, int i, int j, int k) {
    if (i == grid.size() || j == grid[0].size())
      return 0;
    k += grid[i][j] == '(' ? 1 : -1;
    if (k < 0)
      return 0;
    if (i == grid.size() - 1 && j == grid[0].size() - 1)
      return k == 0;
    if (dp[i][j][k] != -1)
      return dp[i][j][k];
    return dp[i][j][k] = hasValidPath(grid, i + 1, j, k) |
                         hasValidPath(grid, i, j + 1, k);
  }
};

 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
class Solution {
  public boolean hasValidPath(char[][] grid) {
    final int m = grid.length;
    final int n = grid[0].length;
    // dp[i][j][k] := 1 if there's a path from grid[i][j] to grid[m - 1][n - 1]
    // w/ # of '(' - # of ')' == k
    dp = new Integer[m][n][m + n];
    return hasValidPath(grid, 0, 0, 0) == 1 ? true : false;
  }

  private Integer[][][] dp;

  private int hasValidPath(char[][] grid, int i, int j, int k) {
    if (i == grid.length || j == grid[0].length)
      return 0;
    k += grid[i][j] == '(' ? 1 : -1;
    if (k < 0)
      return 0;
    if (i == grid.length - 1 && j == grid[0].length - 1)
      return k == 0 ? 1 : 0;
    if (dp[i][j][k] != null)
      return dp[i][j][k];
    return dp[i][j][k] = hasValidPath(grid, i + 1, j, k) | hasValidPath(grid, i, j + 1, k);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def hasValidPath(self, grid: List[List[chr]]) -> bool:
    # dp(i, j, k) := 1 if there's a path from grid[i][j] to grid[m - 1][n - 1]
    # w/ # of '(' - # of ')' == k
    @functools.lru_cache(None)
    def dp(i: int, j: int, k: int) -> int:
      if i == len(grid) or j == len(grid[0]):
        return 0
      k += 1 if grid[i][j] == '(' else -1
      if k < 0:
        return 0
      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)