leetcode/
longest_valid_parentheses.rs

1//! # 32. 最长有效括号
2//!
3//! 难度 困难
4//!
5//! 给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
6//!
7//! ## 示例 1:
8//!
9//! ```text
10//! 输入: "(()"
11//! 输出: 2
12//! 解释: 最长有效括号子串为 "()"
13//! ```
14//!
15//! ## 示例 2:
16//!
17//! ```text
18//! 输入: ")()())"
19//! 输出: 4
20//! 解释: 最长有效括号子串为 "()()"
21//! ```
22//!
23//! See [leetcode](https://leetcode-cn.com/problems/longest-valid-parentheses/)
24//!
25
26use std::cmp::max;
27
28/// Rust 的抽象层次很高，高级抽象，几乎零开销，函数式，高阶函数，
29/// Pattern Matching 这些语法让程序写起来会很简洁，同时也不失去性能。
30///
31/// 主要是用 `Iterator::fold()` 的操作，不用栈，空间 O(1)，
32/// 正反两次迭代，左右相等时记录最大的长度，反向也要执行一次。
33/// 字符串的 `Chars` 本身就是一个双端的迭代器，实现了 `DoubleEndedIterator` 这个 trait，
34/// `rev()` 操作也是零开销。这里为了避免反向遍历的时候左右计数条件要换，
35/// 直接用一个 `map()` 把左右括号对换一下，所以计数的代码就可以直接复用了，
36/// 只要一套从左到右的逻辑。
37pub struct Solution;
38
39impl Solution {
40
41    pub fn longest_valid_parentheses(s: String) -> i32 {
42        let from_left = longest(s.chars());
43        let from_right = longest(s.chars().rev().map(|c| match c {
44            '(' => ')',
45            ')' => '(',
46            _ => unreachable!(),
47        }));
48        max(from_left, from_right) as i32
49    }
50}
51
52fn longest<T: Iterator<Item = char>>(chars: T) -> u32 {
53    chars.fold((0, 0, 0), |(longest, left, right), c| match c {
54        '(' => (longest, left + 1, right),
55        ')' if left == right + 1 => (max(longest, left * 2), left, right + 1),
56        ')' if left > right => (longest, left, right + 1),
57        ')' => (longest, 0, 0),
58        _ => unreachable!(),
59    }).0
60}
61
62#[cfg(test)]
63mod tests {
64    use super::*;
65
66    #[test]
67    fn test() {
68        let cases = vec![
69            (2, "(()(((()"),
70            (4, ")()())"),
71            (4, "(()()"),
72            (6, "((((()))"),
73            (0, ""),
74            (0, "(((("),
75            (0, ")(("),
76            (0, ")))"),
77            (0, ")))("),
78            (2, "()(()"),
79            (2, "(()"),
80            (4, ")()())"),
81            (18, "(((((())))()()()))"),
82            (18, "(()))))))(())))(((((())))()()()))"),
83        ];
84
85        for (expect, s) in cases {
86            assert_eq!(expect, Solution::longest_valid_parentheses(s.into()));
87        }
88    }
89}
leetcode/longest_valid_parentheses.rs

leetcode/
longest_valid_parentheses.rs
