Valid parentheses

Question

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.

问题分析

1. empty string
2. "()[[]]{}((" 是否是valid

Thoughts

对于'(','{',']'，遇到它们时并没有办法判断是否是valid,只有在遇到')','}',']'这些close parenthese时才能与之前的判断是否valid 当前的这个close parenthese与最后出现的open parenthese判断，所以open parenthese是一个LIFO的过程，想到用stack

Solution

class Solution:
    # @param {string} s A string
    # @return {boolean} whether the string is a valid parentheses
    def isValidParentheses(self, s):
        # Write your code here
        if not s:
            return True
        stack = []
        if s[0] == ")" or s[0] == "}" or s[0] == "]":
            return False
        for i in s:
            if i == "(" or i == "{" or i == "[":
                stack.append(i)
            else:
                if not stack:
                    #no open left
                    return False
                openP = stack.pop()
                if i == ")" and openP != "(":
                    return False
                if i == "}" and openP != "{":
                    return False
                if i == "]" and openP != "[":
                    return False
        if stack:
            #still some open parenthese left
            return False
        return True