20. Valid Parentheses

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

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

So, in an essense, we need to match a left bracket with the correct right bracket and leave no open left bracket in the end.

Stack

If we see a right bracket, it must match with the most recent left bracket. This logic leads us to use stack, which has FIFO.

    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        use a stack

        """
        left_side = ('(', '[', '{')
        match = {'(':')', '[':']', '{':'}'}
        stack = []

        for brack in s:
            if brack in left_side:
                stack.append(brack)
            else:
                if not stack:
                    return False
                poped = stack.pop()
                if match[poped] != brack:
                    return False

        if stack:
            return False
        return True

How to make it faster

Remove the left list and use dictionary only

Use dictionary both for matching and check if the current bracket is a left bracket.

Early termination

Odd length

If the length of the bracket list is odd, then we know it is impossible to match successfully so we return False.

Shrink if into one statement

    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        use a stack

        """

        match = {'(':')', '[':']', '{':'}'}
        stack = []

        for brack in s:
            if brack in match:
                stack.append(brack)
            else:
                if not stack or match[stack.pop()] != brack:
                    return False


        return stack == []

Move poping stack and checking if the poped element matches into same line will shorten the code.
Same with the last if statement that return false if the stack is not empty(which means we have unmatched left bracket).

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax