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

1
impl Solution {
2
  pub fn has_valid_path(grid: Vec<Vec<char>>) -> bool {
3
    let (m, n) = (grid.len(), grid[0].len());
4
    // early return if path has odd number of cells or last cell is '('
5
    if ((m + n) & 1 == 0) || grid[m - 1][n - 1] == '(' {
6
      return false;
7
    }
8

9
    // we transform the grid for faster arithmetic
10
    let mut grid: Vec<Vec<i32>> = grid
11
      .into_iter()
12
      .map(|row| {
13
        row
14
          .into_iter()
15
          .map(|c| (c as u8 - b'(') as i32 - (b')' - c as u8) as i32)
16
          .collect()
17
      })
18
      .collect();
19

20
    Self::dfs(&mut grid, &mut vec![vec![vec![false; 199]; n]; m], 0, 0, 0)
21
  }
22

23
  fn dfs(grid: &Vec<Vec<i32>>, dp: &mut Vec<Vec<Vec<bool>>>, y: usize, x: usize, acc: i32) -> bool {
24
    let (m, n) = (grid.len(), grid[0].len());
25
    if y >= m || x >= n || acc > 0 || dp[y][x][(198 + acc) as usize] {
26
      return false;
27
    }
28

29
    if y == m - 1 && x == n - 1 && acc == -1 {
30
      return true;
31
    }
32

33
    let rez = Self::dfs(grid, dp, y, x + 1, acc + grid[y][x])
34
      || Self::dfs(grid, dp, y + 1, x, acc + grid[y][x]);
35

36
    dp[y][x][(198 + acc) as usize] = true;
37
    rez
38
  }
39
}