rustgym/leetcode/
_32_longest_valid_parentheses.rs

1struct Solution;
2
3#[derive(Debug)]
4enum Tok {
5    Left,
6    Pair(i32),
7}
8
9impl Solution {
10    fn longest_valid_parentheses(s: String) -> i32 {
11        let mut res = 0;
12        let mut stack: Vec<Tok> = vec![];
13        for c in s.chars() {
14            if c == '(' {
15                stack.push(Tok::Left)
16            } else {
17                match stack.pop() {
18                    Some(Tok::Left) => {
19                        if let Some(Tok::Pair(x)) = stack.last_mut() {
20                            *x += 2;
21                            res = res.max(*x);
22                        } else {
23                            stack.push(Tok::Pair(2));
24                            res = res.max(2);
25                        }
26                    }
27                    Some(Tok::Pair(x)) => {
28                        if let Some(Tok::Left) = stack.pop() {
29                            if let Some(Tok::Pair(y)) = stack.last_mut() {
30                                *y += x + 2;
31                                res = res.max(*y);
32                            } else {
33                                stack.push(Tok::Pair(x + 2));
34                                res = res.max(x + 2);
35                            }
36                        }
37                    }
38                    None => {}
39                }
40            }
41        }
42        if let Some(Tok::Pair(x)) = stack.pop() {
43            res = res.max(x);
44        }
45        res
46    }
47}
48
49#[test]
50fn test() {
51    let s = "(()".to_string();
52    let res = 2;
53    assert_eq!(Solution::longest_valid_parentheses(s), res);
54    let s = ")()())".to_string();
55    let res = 4;
56    assert_eq!(Solution::longest_valid_parentheses(s), res);
57    let s = "()(())".to_string();
58    let res = 6;
59    assert_eq!(Solution::longest_valid_parentheses(s), res);
60}
rustgym/leetcode/_32_longest_valid_parentheses.rs

rustgym/leetcode/
_32_longest_valid_parentheses.rs
