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

1/**
2 * [2267]  Check if There Is a Valid Parentheses String Path
3 *
4 * A parentheses string is a non-empty string consisting only of '(' and ')'. It is valid if any of the following conditions is true:
5 * 
6 * It is ().
7 * It can be written as AB (A concatenated with B), where A and B are valid parentheses strings.
8 * It can be written as (A), where A is a valid parentheses string.
9 * 
10 * 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:
11 * 
12 * The path starts from the upper left cell (0, 0).
13 * The path ends at the bottom-right cell (m - 1, n - 1).
14 * The path only ever moves down or right.
15 * The resulting parentheses string formed by the path is valid.
16 * 
17 * Return true if there exists a valid parentheses string path in the grid. Otherwise, return false.
18 * 
19 * Example 1:
20 * <img alt="" src="https://assets.leetcode.com/uploads/2022/03/15/example1drawio.png" style="width: 521px; height: 300px;" />
21 * Input: grid = [["(","(","("],[")","(",")"],["(","(",")"],["(","(",")"]]
22 * Output: true
23 * Explanation: The above diagram shows two possible paths that form valid parentheses strings.
24 * The first path shown results in the valid parentheses string "()(())".
25 * The second path shown results in the valid parentheses string "((()))".
26 * Note that there may be other valid parentheses string paths.
27 *
28 * Example 2:
29 * <img alt="" src="https://assets.leetcode.com/uploads/2022/03/15/example2drawio.png" style="width: 165px; height: 165px;" />
30 * Input: grid = [[")",")"],["(","("]]
31 * Output: false
32 * Explanation: The two possible paths form the parentheses strings "))(" and ")((". Since neither of them are valid parentheses strings, we return false.
33 *
34 * 
35 * Constraints:
36 * m == grid.length
37 * n == grid[i].length
38 * 1 <= m, n <= 100
39 * grid[i][j] is either '(' or ')'.
40 * 
41 */
42pub struct Solution {}
43
44// problem: https://leetcode.com/problems/check-if-there-is-a-valid-parentheses-string-path/
45// discuss: https://leetcode.com/problems/check-if-there-is-a-valid-parentheses-string-path/discuss/?currentPage=1&orderBy=most_votes&query=
46
47// submission codes start here
48
49impl Solution {
50    pub fn has_valid_path(grid: Vec<Vec<char>>) -> bool {
51        
52        let m = grid.len();
53        let n = grid[0].len();
54        //println!("size {} and {}", m, n);
55        if grid[0][0] == ')' || grid[m - 1][n - 1] == '(' || (m + n - 1) % 2 == 1 {
56            return false;
57        }
58        
59        return Self::dfs(&grid, 0, 0, (0, 0), &mut vec![vec![vec![0; m + n]; n]; m]);
60    }
61
62    pub fn dfs(grid: &Vec<Vec<char>>, open: usize, close: usize, current: (usize, usize), dp: &mut Vec<Vec<Vec<isize>>>) -> bool {
63        if close > open {
64            return false;
65        }
66
67        if open + close == grid.len() + grid[0].len() - 1  && open == close{
68            return true;
69        }
70
71        if current.0 >= grid.len() || current.1 >= grid[0].len() {
72            return false
73        }
74
75        if dp[current.0][current.1][open - close] > 0 {
76            println!("reuse");
77            if dp[current.0][current.1][open - close] == 1 {
78                return true;
79            } else {
80                return false;
81            }
82        }
83
84        let mut new_open = open;
85        let mut new_close = close;
86        if grid[current.0][current.1] == '(' {
87            new_open = open + 1;
88        } else {
89            new_close = close + 1;
90        }
91
92        //println!("checking ({},{}) with open {} and close {}", current.0, current.1, new_open, new_close);
93
94        dp[current.0][current.1][open - close] = if Self::dfs(&grid, new_open, new_close, (current.0 + 1, current.1), dp) ||
95         Self::dfs(&grid, new_open, new_close, (current.0, current.1 + 1), dp) {1} else {2};
96
97        return dp[current.0][current.1][open - close] == 1;
98    }
99}
100
101// submission codes end
102
103#[cfg(test)]
104mod tests {
105    use super::*;
106
107    #[test]
108    fn test_2267_1() {
109        let grid = vec!(vec!('(','(','('), vec!(')','(',')'), vec!('(','(',')'), vec!('(','(',')'));
110        print!("Got {}", Solution::has_valid_path(grid))
111    }
112
113    #[test]
114    fn test_2267_2() {
115        let grid = vec!(vec!('(','('), vec!(')','('));
116        print!("Got {}", Solution::has_valid_path(grid))
117    }
118
119    #[test]
120    fn test_2267_3() {
121        let grid = vec!(vec!('(','(',')','(',')','(','(',')','(','(',')',')',')',')',')','(',')','(','(',')','(','(',')',')',')',')',')','(','(','(','('),vec!(')','(','(','(',')','(',')','(','(',')',')',')',')','(',')',')','(','(',')',')','(',')','(',')','(','(',')','(',')','(','('),vec!(')',')','(','(',')','(','(',')',')',')',')','(','(',')',')','(',')','(',')',')','(','(','(',')',')',')','(',')',')','(',')'),vec!('(','(',')','(',')','(','(',')','(','(','(',')',')','(',')','(',')',')',')',')',')',')','(','(',')','(',')','(',')','(','('),vec!(')',')','(',')',')','(','(','(',')',')','(',')','(',')',')',')','(','(','(',')',')','(',')','(',')',')','(','(','(','(',')'),vec!(')',')','(','(',')','(',')','(',')','(',')','(',')',')','(',')','(',')',')','(',')','(','(','(',')','(',')',')',')','(','('),vec!(')','(','(','(','(','(','(',')',')','(','(',')','(',')',')','(',')',')',')','(','(','(',')','(','(',')',')','(',')','(',')'),vec!(')',')','(','(','(','(','(','(','(',')',')','(','(','(','(','(','(','(','(','(','(','(','(',')',')','(','(',')',')','(',')'),vec!('(',')',')',')','(','(',')',')',')',')','(',')',')','(',')',')','(','(','(','(','(','(','(',')',')','(','(',')',')','(','('),vec!('(','(',')','(',')',')',')',')','(','(','(',')',')',')','(',')','(','(',')','(','(','(',')','(','(','(','(','(',')',')',')'),vec!('(',')','(','(','(','(',')','(','(',')',')','(','(',')','(','(','(',')','(','(','(',')',')','(',')',')','(',')','(','(',')'),vec!(')',')','(','(','(','(',')','(','(',')',')','(',')',')','(',')','(','(','(','(','(','(','(',')','(','(',')',')','(','(','('),vec!('(',')',')',')','(',')','(','(','(',')',')',')','(',')','(',')',')','(','(','(','(',')','(',')',')',')',')',')',')','(','('),vec!('(','(','(','(','(','(',')',')','(',')','(','(','(',')',')','(',')','(',')','(',')','(','(','(',')',')',')','(',')','(','('),vec!('(',')',')',')',')','(','(',')',')',')',')',')',')','(','(',')','(',')',')','(',')','(',')',')',')','(','(',')','(','(','('),vec!('(',')',')','(','(',')',')','(',')',')','(','(','(',')',')',')',')','(','(','(',')',')','(',')','(','(','(','(',')',')',')'),vec!(')','(','(',')','(','(',')',')',')','(','(','(','(',')','(',')',')',')','(',')','(',')','(','(',')','(','(','(','(','(','('),vec!('(',')','(',')','(','(',')',')',')',')',')','(','(',')',')','(',')','(',')',')',')',')','(','(','(',')','(',')','(',')',')'),vec!('(',')','(',')',')',')','(','(','(',')','(',')','(','(',')',')','(',')','(',')','(',')','(','(','(','(','(',')','(',')','('),vec!(')',')',')',')',')','(',')',')','(','(',')','(',')',')','(',')',')','(','(','(','(',')','(','(','(','(',')',')',')',')','('),vec!(')','(','(','(','(','(',')','(',')',')',')',')','(','(','(',')',')','(',')',')','(','(','(','(','(','(',')',')','(','(','('),vec!('(','(','(',')',')','(',')','(',')',')',')',')','(',')',')',')',')','(',')','(','(','(','(',')','(','(','(','(','(','(',')'));
122        print!("Got {}", Solution::has_valid_path(grid))
123    }
124}
125