Check if there is a valid parentheses string path

Array Dynamic Programming Matrix

40.1% acceptance

Feb 25, 2026

541

A parentheses string is a non-empty string consisting only of '(' and ')'. It is valid if any of the following conditions is true: It is (). It can be written as AB (A concatenated with B), where A and B are valid parentheses strings. It can be written as (A), where A is a valid parentheses string. You are given an m x n matrix of parentheses grid. A valid parentheses string path in the grid is a path satisfying all of the following conditions: The path starts from the upper left cell (0, 0). The path ends at the bottom-right cell (m - 1, n - 1). The path only ever moves down or right. The resulting parentheses string formed by the path is valid. Return true if there exists a valid parentheses string path in the grid. Otherwise, return false.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn has_valid_path(grid: Vec<Vec<char>>) -> bool {
    let m = grid.len();
    let n = grid[0].len();
    // Path length = m+n-1; must be even
    if (m + n) % 2 == 0 { return false; }
    // dp[r][c] = bitmask of achievable balance values (need 100 bits, use u128)
    let mut dp = vec![vec![0u128; n]; m];
    // Start: cell (0,0)
    let b0: i32 = if grid[0][0] == '(' { 1 } else { -1 };
    if b0 >= 0 { dp[0][0] = 1u128 << b0; }

    for r in 0..m {
      for c in 0..n {
        if r == 0 && c == 0 { continue; }
        let mut mask = 0u128;
        if r > 0 { mask |= dp[r-1][c]; }
        if c > 0 { mask |= dp[r][c-1]; }
        if mask == 0 { continue; }
        dp[r][c] = if grid[r][c] == '(' {
          // All balances shift up by 1, mask out >= 100
          (mask << 1) & ((1u128 << 100) - 1)
        } else {
          // All balances shift down by 1, drop balance 0 (would go negative)
          mask >> 1
        };
      }
    }
    // Check if balance 0 achievable at (m-1,n-1)
    dp[m-1][n-1] & 1 != 0
  }
}