20. Valid Parentheses

https://leetcode.com/problems/valid-parentheses

Python

N = len(s) O(logN)

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2 != 0:
            return False

        brackets = {
            ")": "(",
            "]": "[",
            "}": "{",
        }
        lefts = brackets.values()
        rights = brackets.keys()


        stack = []

        for char in s:
            if char in lefts:
                stack.append(char)
                continue

            if char in rights:
                if not stack:
                    return False

                if brackets[char] == stack[-1]:
                    stack.pop()
                    continue
                return False

            # Corner case, should never happen
            return False

        return not bool(stack)

Rust

use std::collections::HashMap;


impl Solution {
    pub fn is_valid(s: String) -> bool {
        let brackets: HashMap<char, char> = [('(', ')'), ('[', ']'), ('{', '}')].into_iter().cloned().collect();

        let mut stack = Vec::new();

        for letter in s.chars() {
            match brackets.get(&letter) {
                Some(opposite) => {
                    stack.push(*opposite)
                },
                None => {
                    if stack.pop() != Some(letter) {
                        return false
                    }
                }
            }
        }
        stack.is_empty()
    }
}