Valid Parentheses

I did this problem from Leetcode. Here was my first solution:

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        '''
        arr = []

        for i in range(len(s)):
            if s[i] == '(':
                arr.append(s[i])
            if s[i] == '{':
                arr.append(s[i])
            if s[i] == '[':
                arr.append(s[i])
            if s[i] == ')':
                if not arr or (arr.pop() != '('):
                    return False
            if s[i] == '}':
                if not arr or (arr.pop() != '{'):
                    return False
            if s[i] == ']':
                if not arr or (arr.pop() != '['):
                    return False

        if arr:
            return False
        return True'''

My first attempt was hard coding it and adding a lot of checks. It works but we can improve it.

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """

        Map = {")": "(", "]": "[", "}": "{"}
        stack = []
        for c in s:
            if c not in Map:
                stack.append(c)
            if c in Map:
                if not stack or stack[-1] != Map[c]:
                    return False
                stack.pop()

        return not stack

My second attempt utilized a map and this made things a lot easier. We took advantage of the fact that once we see an end parenthesis, we will never see an open parenthesis again. This means we can map end to beginning and pop the stack.

Previous
Previous

Min Stack

Next
Next

Baseball Game