Function is_valid

pub fn is_valid(s: String) -> bool

Solutions

Approach 1: Stacks

• Time complexity: O(n)

• Space complexity: O(n)

use std::collections::HashMap;

impl Solution {
    pub fn is_valid(s: String) -> bool {
        let mut v = vec![];
        let mut str_map: HashMap<char, char> = HashMap::new();
        str_map.insert(')', '(');
        str_map.insert('}', '{');
        str_map.insert(']', '[');

        for s1 in s.chars() {
            if str_map.contains_key(&s1) {
                if v.pop() != Some(str_map[&s1]) {
                    return false;
                }
            } else {
                v.push(s1)
            }
        }

        v.is_empty()
    }
}

Approach 2: Stacks

• Time complexity: O(n)

• Space complexity: O(n)

impl Solution {
    pub fn is_valid(s: String) -> bool {
        let mut stack = vec![];
        for c in s.chars() {
            match c {
                '(' => stack.push(')'),
                '{' => stack.push('}'),
                '[' => stack.push(']'),
                ')' | '}' | ']' => {
                    match stack.pop() {
                        None => return false,
                        Some(ch) => { if ch != c { return false; }},
                    }
                },
                _ => {},
            }
        }
        stack.is_empty()
    }
}