Problem of The Day: Valid Parentheses

Problem Statement

leetcode problem link

Solution [Accepted]

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        mapping = {
            ')':'(',
            '}':'{',
            ']':'['
        }
        for c in s:
            if c in mapping:
                if not stack:
                    return False
                if stack:
                    curr = stack.pop()
                    if curr != mapping[c]:
                        return False
            else:
                stack.append(c)

        return len(stack) == 0

Time: O(N) Space: O(N)

public class Solution {
    public bool IsValid(string s) {
        Stack<char> stack = new Stack<char>();
        Dictionary<char, char> mapping = new Dictionary<char, char> {
            {')', '('},
            {'}', '{'},
            {']', '['}
        };
        foreach (var ch in s) {
            if (mapping.ContainsKey(ch)) {
                if (stack.Count == 0) {
                    return false;
                }
                if (stack.Count > 0) {
                    var currOpen = stack.Pop();
                    if (currOpen != mapping[ch]) {
                        return false;
                    }
                }
            } else {
                stack.Push(ch);
            }
        }

        return stack.Count == 0;
    }
}

Editorial

Approach 1: Stacks

class Solution(object):
    def isValid(self, s: str) -> bool:

        # The stack to keep track of opening brackets.
        stack = []

        # Hash map for keeping track of mappings. This keeps the code very clean.
        # Also makes adding more types of parenthesis easier
        mapping = {")": "(", "}": "{", "]": "["}

        # For every bracket in the expression.
        for char in s:

            # If the character is an closing bracket
            if char in mapping:

                # Pop the topmost element from the stack, if it is non empty
                # Otherwise assign a dummy value of '#' to the top_element variable
                top_element = stack.pop() if stack else "#"

                # The mapping for the opening bracket in our hash and the top
                # element of the stack don't match, return False
                if mapping[char] != top_element:
                    return False
            else:
                # We have an opening bracket, simply push it onto the stack.
                stack.append(char)

        # In the end, if the stack is empty, then we have a valid expression.
        # The stack won't be empty for cases like ((()
        return not stack

public class Solution {
    private Dictionary<char, char> mappings;

    public Solution() {
        mappings = new Dictionary<char, char> {
            { ')', '(' }, { '}', '{' }, { ']', '[' }
        };
    }

    public bool IsValid(string s) {
        var stack = new Stack<char>();
        foreach (var c in s) {
            if (mappings.ContainsKey(c)) {
                char topElement = stack.Count == 0 ? '#' : stack.Pop();
                if (topElement != mappings[c]) {
                    return false;
                }
            } else {
                stack.Push(c);
            }
        }

        return stack.Count == 0;
    }
}