Rust Interview Puzzles: Valid brackets

Problem

We need to check if a provided string str containing brackets {}[]() is syntactically valid. It means that all brackets are complete and in the correct order. The string could not contain characters other than {}[]().

Examples:

Solution

fn has_string_valid_brackets(str: &str) -> bool {
    const OPEN_BRACKETS: &str = "{[(";
    const CLOSE_BRACKETS: &str = "}])";
    let mut stack = Vec::new();

    for char in str.chars() {
        if OPEN_BRACKETS.contains(|c| c == char) {
            stack.push(char)
        } else if CLOSE_BRACKETS.contains(|c| c == char) {
            let popped = stack.pop();
            match (popped, char) {
                (Some('('), ')') | (Some('{'), '}') | (Some('['), ']') => continue,
                _ => return false,
            }
        } else {
            panic!("the input string must only contain brackets!")
        }
    }

    return stack.is_empty();
}

Explanation

For a string to be syntactically valid, it needs to have brackets in the correct order and no brackets could be missing. In other words, every opening bracket should be timely followed by a corresponding closing bracket. If that is the case for all characters in the string - then the string is valid. The Stack data structure (represented by Vec in our implementation) is ideal for this scenario.

While iterating over the string characters char we check if this char is an opening bracket. If yes - we push it to the stack. If it is a closing bracket then we pop the last opening bracket (popped) from the stack. If the popped opening bracket corresponds to the current closing bracket char, then all is good and so far the string is valid. Otherwise, we return false right away.

At the end of the function, the stack should be empty for a valid string.

Complexity

The time complexity of this solution is O(n) (where n is a number of the characters in the string). The auxiliary space complexity is O(n) because we used the stack data structure to solve the puzzle.

---

Rust Playground with this code