[−][src]Function leetcode_for_rust::cd0020_valid_parentheses::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() } }