1190. Reverse Substrings Between Each Pair of Parentheses Medium

1/**
2 * [1190] Reverse Substrings Between Each Pair of Parentheses
3 *
4 * You are given a string s that consists of lower case English letters and brackets.
5 * Reverse the strings in each pair of matching parentheses, starting from the innermost one.
6 * Your result should not contain any brackets.
7 *  
8 * Example 1:
9 *
10 * Input: s = "(abcd)"
11 * Output: "dcba"
12 *
13 * Example 2:
14 *
15 * Input: s = "(u(love)i)"
16 * Output: "iloveu"
17 * Explanation: The substring "love" is reversed first, then the whole string is reversed.
18 *
19 * Example 3:
20 *
21 * Input: s = "(ed(et(oc))el)"
22 * Output: "leetcode"
23 * Explanation: First, we reverse the substring "oc", then "etco", and finally, the whole string.
24 *
25 *  
26 * Constraints:
27 *
28 * 1 <= s.length <= 2000
29 * s only contains lower case English characters and parentheses.
30 * It is guaranteed that all parentheses are balanced.
31 *
32 */
33pub struct Solution {}
34
35// problem: https://leetcode.com/problems/reverse-substrings-between-each-pair-of-parentheses/
36// discuss: https://leetcode.com/problems/reverse-substrings-between-each-pair-of-parentheses/discuss/?currentPage=1&orderBy=most_votes&query=
37
38// submission codes start here
39
40impl Solution {
41    pub fn reverse_parentheses(s: String) -> String {
42        Self::rev(&mut s.chars())
43    }
44
45    fn rev(chs: &mut std::str::Chars) -> String {
46        let mut result = String::new();
47        while let Some(x) = chs.next() {
48            if x == '(' {
49                let next = Self::rev(chs);
50                result = [result, next].concat();
51            } else if x == ')' {
52                return result.chars().rev().collect();
53            } else {
54                result.push(x);
55            }
56        }
57
58        result
59    }
60}
61
62// submission codes end
63
64#[cfg(test)]
65mod tests {
66    use super::*;
67
68    #[test]
69    fn test_1190() {
70        assert_eq!(
71            Solution::reverse_parentheses("(ed(et(oc))el)".to_string()),
72            "leetcode".to_owned()
73        );
74    }
75}
76