20.Valid Parentheses

Tags: [stack], [parentheses], [parenthesis]

Com: {fb}

Link: https://leetcode.com/problems/valid-parentheses/\#/description

Given a string containing just the characters'(',')','{','}','['and']', determine if the input string is valid.

The brackets must close in the correct order,"()"and"()[]{}"are all valid but"(]"and"([)]"are not.

Solution: Stack

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

        stack = []
        index = 0
        while index < len(s):
            curr = s[index]
            if curr in ('(', '[', '{'):
                stack.append(curr)
            else:
                if not stack:
                    return False
                left_p = stack.pop()
                if (curr == ')' and left_p != '(') or (curr == ']' and left_p != '[') or (curr == '}' and left_p != '{'):
                    return False

            index += 1

        return len(stack) == 0

Note:

• Time complexity = O(n), n is the length of the given string.
• Space complexity = O(n), n is the length of the given string.