pub fn is_valid(s: String) -> bool
Expand description
§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()
}
}