Solution > Leetcode 1190. Reverse Substrings Between Each Pair of Parentheses

[axobel]

Typical... I was searching for something and accidentally landed this Leetcode problem and thought I could solve it quickly, but it wasn't to be. I wanted to use recursion and ended up muddling up and having to think about it some more. In the process, I saw various solutions from many different languages and I think the Rust solution I ended up with is much more elegant🤣I couldn't find anywhere to post this so I decided to post it here. Maybe, it can help other Rust users attacking the problem.

It's not really a code review so to speak, but if anyone has any comments or suggestions I am happy to hear them.If there is a better category for this, let me know. I kept the function definition the same as the Leetcode definition and have longer (more descriptive) variables than I normally would...

fn main() {
    // println!("{}", reverse("(ed(et(oc))el)".to_string()));
    println!("{}", reverse_parentheses("The ((quick (brown) (fox) jumps over the lazy) dog)".to_string()));
}

fn reverse_parentheses(s: String) -> String {
    // stop recursion and return when there are no closing brackets remaining
    if !s.contains(')') {
        return s.to_string();
    }

    let mut buf = String::new();
    let mut open_bracket_indicies = Vec::new();

    for (current_index, c) in s.chars().enumerate() {
        match c {
            '(' => open_bracket_indicies.push(current_index),
            ')' => {
                if let Some(open_bracket_index) = open_bracket_indicies.pop() {

                    // build new string with inner most bracket group reversed and brackets removed for recursion
                    buf.push_str(&s[..open_bracket_index]);
                    buf.push_str(&s[open_bracket_index + 1..current_index].chars().rev().collect::<String>());
                    buf.push_str(&s[current_index + 1..]);

                    // only process first closing bracket (recursion handles the others)
                    break;
                }
            }
            _ => (),
        }
    }

    reverse_parentheses(buf)
}

[H2CO3]

You can further simplify this by observing that finding the innermost balanced parentheses is easily done by looking for the first closing parenthesis from the left and matching it with the immediately preceding opening parenthesis (or equivalently, by finding the last opening parenthesis and matching it with the immediately following closing parenthesis):

fn reverse_in_parens(s: &mut Vec<u8>) {
    while let Some(j) = s.iter().position(|&x| x == b')') {
        let i = s[..j].iter().rposition(|&x| x == b'(').expect("innermost paren imbalanced");
        let contents: Vec<_> = s[i+1..j].iter().rev().copied().collect();
        s.splice(i..=j, contents);
    }
}

Playground

Or with re-use of the temporary buffer:

fn reverse_in_parens(s: &mut Vec<u8>) {
    let mut contents = Vec::new();
    while let Some(j) = s.iter().position(|&x| x == b')') {
        let i = s[..j].iter().rposition(|&x| x == b'(').expect("innermost paren imbalanced");
        contents.clear();
        contents.extend(s[i+1..j].iter().rev());
        s.splice(i..=j, contents.drain(..));
    }
}

[quinedot]

char_indices exists.

You don't need a Vec since you only pop once; you can use an Option. You also don't need to scan for ')' twice if you return from the "do something" arm and return the input at the end of the function. (This does change behavior of the degenerate case of unbalanced parens (I didn't read the problem statement).) Playground.

I too thought of the what @H2CO3 noted and here's another formulation for that. It could be simplified if unbalanced parens are not a concern.

[axobel]

Both suggestions have shown me new ways of doing things. The most useful to me are the iterator and vector methods.. sometimes it's difficult to find these things unless you know what you are looking for. I think that my version shows that I am not yet "dreaming" in Rust (that's my indicator that I have started to absorb verbal languages) and still have the baggage of many years of using other (inferior ) languages.

Thanks!